[Kotlin] 백준 2178 (ft. BFS)

📚 백준 2178

BFS 문제

직접 풀어보려는 사람들을 위해 접근 방법에 대한 힌트부터 작성한다.

전체 코드는 최하단을 확인 바람

 

---

 

미로 탐색 문제 유형을 채험해 보는데 가장 좋은 문제라고 생각된다.

일반적으로 이런 문제는 큐(Queue)에 현재 위치의 행과 열의 인덱스를 저장한다.

이 문제의 경우, 각 칸을 방문할 때마다 해당 칸까지 이동하는 데 필요한 최소 이동 횟수를 계산하면 된다.

 

나는 위치 정보 저장을 위한 큐(Queue)와 이동 횟수 저장을 위한 2차원 List를 사용했다.

그리고 현 위치를 기준으로 상하좌우 한칸씩만 검사해주며 진행하는 방식으로 풀었다.

큐에 저장할 값

- 위치 정보: 현재 위치의 행과 열 인덱스, 예를 들어 현재 위치가 2행 3열이면, Pair(2, 3)으로 큐에 저장했다.

2차원 리스트에 저장할 값

- 각 위치에 도달하기까지의 이동 횟수를 저장

 

구현 방법

1. 초기설정

시작 위치(0, 0)을 큐에 추가한다. 이 때, 시작 위치의 이동 횟수는 1로 설정한다.

 

2. BFS 실행

큐가 빌 때 까지 다음의 과정을 반복한다.

- 큐에서 하나의 위치를 꺼냄, 이 때, 해당 위치에 기록된 이동 횟수도 변수에 저장 해둠

- 해당 위치에서 상하좌우로 인접한 칸 중 이동 가능한 칸을 찾아 큐에 추가

- 이동 가능한 칸의 인덱스를 가져와 2차원 리스트에서 이동 횟수를 +1해서 저장

 

 

코드

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    var arr = arrayListOf<List<Int>>()

    repeat(n) {
        val line = readln().map { it.toString().toInt() }
        arr.add(line)
    }

    val queue = ArrayDeque<Pair<Int, Int>>()
    val cntArr = MutableList(n) { MutableList(m) { 0 } }
    queue.addLast(Pair(0, 0))
    cntArr[0][0] = 1
    while (queue.isNotEmpty()) {
        val (x, y) = queue.removeFirst()
        val cnt = cntArr[x][y]

        if (x > 0 && arr[x - 1][y] == 1 && cntArr[x - 1][y] == 0) {
            queue.addLast(Pair(x - 1, y))
            cntArr[x - 1][y] = cnt + 1
        }
        if (x < n - 1 && arr[x + 1][y] == 1 && cntArr[x + 1][y] == 0) {
            queue.addLast(Pair(x + 1, y))
            cntArr[x + 1][y] = cnt + 1
        }
        if (y > 0 && arr[x][y - 1] == 1 && cntArr[x][y - 1] == 0) {
            queue.addLast(Pair(x, y - 1))
            cntArr[x][y - 1] = cnt + 1
        }
        if (y < m - 1 && arr[x][y + 1] == 1 && cntArr[x][y + 1] == 0) {
            queue.addLast(Pair(x, y + 1))
            cntArr[x][y + 1] = cnt + 1
        }
    }

    println(cntArr[n - 1][m - 1])
}