[백준 2667번] [Kotlin] 단지번호붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

난이도 : 실버 1
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

1. 설명

좌표 상 각 블록(단지)의 개수가 몇개인지 판단하는 전형적인 그래프 탐색 (DFS / BFS) 문제입니다.

모든 점에 대해 DFS / BFS를 진행하며, DFS / BFS가 진행된 횟수를 카운트하면 됩니다.

 

DFS 및 BFS 중 어느것을 사용해 풀이해도 무방하나,

이전 코테 포스팅에서 DFS는 많이 풀이해봤기에 이번엔 BFS로 한번 풀이해보겠습니다.

 

 

2. 소스코드

2.1. 좌표를 담을 데이터 클래스와 dx, dy

      

      

      

    
    

      <code />
    
data class Node(val x: Int, val y: Int)

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

좌표를 담을 데이터 클래스 Node를 생성합니다.

그리고 방향 이동을 도와줄 dx와 dy를 생성합니다.

 

2.2. 인풋값 저장

      

      

      

    
    

      <code />
    
val br = BufferedReader(InputStreamReader(System.`in`))
val n = br.readLine().toInt()

val map = Array(n) { Array(n) { 0 } }

repeat(n) { x ->
    val input = br.readLine()
    repeat(n) { y ->
        map[x][y] = input[y] - '0'
    }
}

맵의 각 좌표에 인풋값을 저장합니다.

 

 

2.3. BFS

      

      

      

    
    

      <code />
    
var blockCnt = 0
val cntPerBlock = ArrayList<Int>()

for (x in 0 until n) {
    for (y in 0 until n) {
        if (map[x][y] == 0) continue

        val queue: Queue<Node> = LinkedList()
        queue.offer(Node(x, y))
        map[x][y] = 0
        var cntThisBlock = 1

        while (queue.isNotEmpty()) {
            val target = queue.poll()

            for (i in 0 until 4) {
                val nx = target.x + dx[i]
                val ny = target.y + dy[i]

                if (nx !in 0 until n || ny !in 0 until n || map[nx][ny] == 0 )
                    continue

                queue.offer(Node(nx, ny))
                map[nx][ny] = 0
                cntThisBlock++
            }
        }

        blockCnt++
        cntPerBlock.add(cntThisBlock)
    }
}

이제 맵의 모든 좌표에 대해 BFS를 실행합니다.

 

 

 

BFS 과정을 천천히 살펴 보겠습니다.

      

      

      

    
    

      <code />
    
var blockCnt = 0
val cntPerBlock = ArrayList<Int>()

blockCnt는 이 맵이 몇개의 블록으로 이루어졌는가를 담을 변수이며,

cntPerBlock은 한 블록당 몇개의 좌표로 이루어져 있는지를 담을 리스트입니다.

 

      

      

      

    
    

      <code />
    
if (map[x][y] == 0) continue

 

만약, 좌표의 값이 0이라면 다음 케이스로 넘어갑니다. 

 

 

      

      

      

    
    

      <code />
    
val queue: Queue<Node> = LinkedList()
queue.offer(Node(x, y))
map[x][y] = 0
var cntThisBlock = 1

큐에 시작 좌표값을 넣고, 해당 좌표값을 0으로 만들어줍니다.

cntThisBlock은 현재 블록이 몇개의 좌표로 이루어져있는가를 담을 변수입니다.

 

 

      

      

      

    
    

      <code />
    
while (queue.isNotEmpty()) {
    val target = queue.poll()

    for (i in 0 until 4) {
        val nx = target.x + dx[i]
        val ny = target.y + dy[i]

        if (nx !in 0 until n || ny !in 0 until n || map[nx][ny] == 0 )
            continue

        queue.offer(Node(nx, ny))
        map[nx][ny] = 0
        cntThisBlock++
    }
}

while문 내부는 다른 BFS와 별 다른점은 없습니다.

다만, 좌표 하나를 방문처리 할 때마다 cntThisBlock의 값을 1씩 늘려줍니다.

 

 

      

      

      

    
    

      <code />
    
blockCnt++
cntPerBlock.add(cntThisBlock)

큐가 비어 While문을 빠져나오면 (BFS가 끝나면)

전체 블록의 갯수(blockCnt)를 1 증가시키고,

한 블럭당 좌표의 개수를 담는 리스트인 cntPerBlock에 현재 블록의 좌표개수를 넣어줍니다.

 

      

      

      

    
    

      <code />
    
println(blockCnt)
cntPerBlock.sorted().forEach { println(it) }

마지막으로 블록의 개수와 각 블록이 몇개의 좌표로 이루어졌는지를 정렬하여 출력합니다.

 

 

 

2.4. 전체 소스코드

      

      

      

    
    

      <kotlin />
    
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Node(val x: Int, val y: Int)

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()

    val map = Array(n) { Array(n) { 0 } }

    repeat(n) { x ->
        val input = br.readLine()
        repeat(n) { y ->
            map[x][y] = input[y] - '0'
        }
    }
    var blockCnt = 0
    val cntPerBlock = ArrayList<Int>()

    for (x in 0 until n) {
        for (y in 0 until n) {
            if (map[x][y] == 0) continue

            val queue: Queue<Node> = LinkedList()
            queue.offer(Node(x, y))
            map[x][y] = 0
            var cntThisBlock = 1

            while (queue.isNotEmpty()) {
                val target = queue.poll()

                for (i in 0 until 4) {
                    val nx = target.x + dx[i]
                    val ny = target.y + dy[i]

                    if (nx !in 0 until n || ny !in 0 until n || map[nx][ny] == 0 )
                        continue

                    queue.offer(Node(nx, ny))
                    map[nx][ny] = 0
                    cntThisBlock++
                }
            }

            blockCnt++
            cntPerBlock.add(cntThisBlock)
        }
    }

    println(blockCnt)
    cntPerBlock.sorted().forEach { println(it) }
}

 

 

 

3. 후기

전형적인 그래프 탐색 문제였습니다.

Solved.ac의 클래스 2~3을 풀고 있는데,

어째 DFS / BFS 문제가 꽤 많은 것 같습니다.