백준 2667번 단지 번호 붙이기 - Kotlin

오늘은 그래프 탐색 중 단지 번호 붙이기를 풀어보았습니다. 그래프 탐색으로 분류되어 있지만 사실 BFS&DFS와 비슷한 문제 같은 카테고리로 묶어도 될듯하다. 따지고 보면 BFS&DFS가 그래프 탐색에 포함되어 있는 게 맞겠지.

일단 문제부터 보자

​

문제

​

접근 방법

전에 풀어본 BFS&DFS 때문인지 저런 2차원 배열의 형태의 맵을 보고 자연스럽게 BFS&DFS로 풀이해야겠다는 생각을 했다. 그중 BFS를 선택했고 기억을 더듬어 풀었기에 조금 헤매느라 시간이 좀 걸렸다.

하지만 결국 정답을 거머쥐었다.

소스를 확인해보자.

​

풀이 소스

import java.io.BufferedReader
import java.io.InputStreamReader

val dx = arrayListOf(0, 1, 0, -1)
val dy = arrayListOf(1, 0, -1, 0)
var answer = mutableListOf<Int>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    val map = Array(size) { Array(size, { 0 }) }

    for (i in 0 until size) {
        val line = readLine()
        for (j in 0 until size) {
            map[i][j] = line[j].toInt() - 48
        }
    }

    for (i in 0 until size) {
        for (j in 0 until size) {
            if (map[i][j] == 1) {
                bfs(size, i, j, map)
            }
        }
    }
//정답출력
    println(answer.size)
    answer.sorted().forEach { println(it) }
}

fun bfs(size: Int, N: Int, M: Int, map: Array<Array<Int>>) {
    val queue = mutableListOf<Pair<Int, Int>>()  //큐를 저장하기 위한 페어 리스트
    var count = 0 //단지의 집 개수 카운트 변수
    val visited = Array(size) { Array(size, { 0 }) } //방문 확인용 0이면 미방문 1이면 방문

    queue.add(Pair(N, M)) //큐에 좌표추가
    visited[N][M] = 1    //들어온 좌표 방문표시

    while (!queue.isEmpty()) { //큐가 빌 때까지
        var temp = queue.removeAt(0) //큐내용 저장 후 큐 헤드 삭제

        for (i in 0 until 4) {
            val move_x = temp.first + dx[i]
            val move_y = temp.second + dy[i]

            if (move_x in 0 until size &&   //맵크기를 벗어나지 않고
                move_y in 0 until size &&
                map[move_x][move_y] == 1 &&  //집이면서
                visited[move_x][move_y] == 0 //아직 방문을 안했으면
            ) {
                queue.add(Pair(move_x, move_y))  //큐에 좌표 추가
                visited[move_x][move_y] = 1      //방문표시
                map[move_x][move_y] = 0          //집표시 삭제( main의 이중for문에서 bfs호출 중복방지을 위해)
            }
        }
        count++  //집 개수 증가
    }
    answer.add(count)  //정답리스트에 집 개수 추가
}

사실 첫 제출을 했을 때 오답이 나왔다

그냥 아무 힌트도 없이 달랑 '틀렸습니다'라는 문구만 적혀있으니 대체 뭐 때문에 틀린 지를 모르겠는 상황....

문명 IDE에서는 문제없이 정답이 잘 출력되는데 말이지...

그래서 한참을 고민하다가 문제를 다시 한번 꼼꼼히 읽어봤다. 두어 번 다시 읽어보니 놓치고 있던 문제의 조건을 캐치했고 그것은 바로!!

그렇다 정렬을 하라는 조건이 있었는데 이 부분을 놓치고 있었다. 그래서 바로 수정 소스는 아래 소스이다

answer.forEach { println(it) } ======>>>>>>> answer.sorted().forEach { println(it) }

​

문제점을 바로잡고 제출을 하여 마침내 정답을 받아내었다.

답을 맞힌 뒤 내 소스의 순위를 살펴보았지만. 정답자들 중 채점기준 뒤에서 두 번째라는 절망스러운 현실이었다.....

​

마침

힘들게 답을 맞히기는 하였지만 낮은 순위에 살짝 당황하였고,, 다른 풀 이자들의 소스를 보았다....

​

아.. 내가 잘못 접근하였구나... 그렇다 이 문제는 BFS가 아닌 DFS로 풀어야 하는 문제였나 보다...

다른 풀 이자들은 나 빼고 죄다 DFS였다..

나중에 DFS로 풀어 본뒤 다시 게시해야겠다....

결국 이번 문제는 답을 맞혔지만 문제에 대한 올바른 분석을 하지 못한 것이다.

앞으로는 이런 일이 없도록 문제를 정확하게 분석하고 접근하는 방법을 열심히 모색해야겠다.