백준 1261번: 알고스팟 (Kotlin)

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

1261번: 알고스팟

안녕하세요, 이륙사입니다.

 

풀이1

이번 문제는 BFS를 활용하는 그래프 탐색 문제였습니다.

 

기본적인 BFS와는 문제와는 다른 점이 있는데요. 특정 위치에 최단거리로 가는 것이 아닌, 최소로 벽을 부수면서 간다는 것입니다. BFS의 특징은 가까운 순서대로 한번만 방문하면서 모든 위치를 방문할 수 있다는 것입니다. 하지만 이 문제에서 BFS를 그냥 사용하면, 이동 방향의 우선순위에 따라 벽을 더 많이 부수는 경로가 특정 위치에 먼저 도착할 수 있습니다.  

 

이런 문제를 해결하기 위해 특정 위치에 도착할 때마다 그때까지 부셨던 벽의 개수를 기록합니다. 그리고 새로운 경로에서 방문을 시도할 때, 갱신을 시도하는 값이 작을 때만 재방문을 허용합니다. 그러면 언젠가는 모두 최소 값으로 갱신되기 때문에 정답을 찾을 수 있습니다. 미로 크기가 100 * 100이라서 몇 번의 재탐색이 일어나라도 충분히 시간 안에 해결할 수 있습니다.

// 경로를 지나면서 벽을 몇 개 부셨는지 기록,
// 큰 값으로 초기화해서 처음 방문할 때는 항상 방문하면서 갱신하게 한다
val brokenCountAt = Array(maze.size) {
        IntArray(maze[0].size) { 10_000 }
    }
    
    ....

// 벽을 부셔야하는 상황에서 기존에 기록된 경로 값이 지금의 경로 값이 값보다 크다면 재탐색한다
            if (maze[nextRow][nextCol] == '1' && brokenCountAt[nextRow][nextCol] > brokenCountAt[row][col] + 1) {
                brokenCountAt[nextRow][nextCol] = brokenCountAt[row][col] + 1
                q.add(Pair(nextRow, nextCol))
            }
            // 벽을 부시지 않아도 되지만, 기존 경로 값이 지금 경로 값보다 크면 재탐색
            else if (maze[nextRow][nextCol] == '0' && brokenCountAt[nextRow][nextCol] > brokenCountAt[row][col]) {
                brokenCountAt[nextRow][nextCol] = brokenCountAt[row][col]
                q.add(Pair(nextRow, nextCol))
            }

 

참고로 DFS를 사용하면 한 방향으로 먼저 끝까지 탐색하고 돌아오는데, 다 탐색하고 왔더니 최소 경로가 아니라서 모두 재탐색을 해야하는 경우가 발생할 수 있기 때문에 BFS를 사용하는 것이 좋습니다.

 

풀이2

생각해보니 다익스트라 알고리즘이랑 아주 비슷한 것 같습니다. 사실 다익스트라랑 똑같습니다!ㅋㅋ 0과 1의 가중치를 갖고 있는 그래프 탐색 문제로 생각할 수 있습니다.

 

풀이1에서 문제가 됐던 건 무작정 탐색하면 최소로 벽을 부수는(최소 누적 가중치) 경로가 나오지 않는다는 거였습니다.이제 그 이유를 알 수 있는데요, 이동할 때 가중치를 고려하지 않았기 때문입니다. 문제에서 찾고자 하는 건 최소 가중치를 갖는 경로입니다. 따라서, 움직일 때마다 가중치가 작은 방향을 우선으로 탐색하면 특정 위치를 최소 누적 가중치를 갖고 최초로 방문할 수 있습니다. 

 

이러한 방식으로 구현하기 위해 2가지 방법을 사용할 수 있습니다. 하나는 우선순위 큐를 사용하는 것이고, 다른 하나는 양방향 큐를 사용하는 것입니다. 양방향 큐를 사용하는 경우 0을 탐색할 때는 큐의 앞쪽에, 1을 탐색할 때는 큐의 뒤쪽에 넣으면서 진행합니다. 그러면 항상 누적 가중치가 작은 경로를 전부 탐색한 후에, 그 다음 누적 가중치가 큰 경로들을 탐색하기 때문에 모든 위치를 최소 경로로 한번만 지날 수 있습니다. 

val brokenCountAt = Array<IntArray>(rowSize) { // 벽을 부순 횟수를 기록 + 방문 여부 표시 역할
        IntArray(colSize) { -1 }
    }
    
    ....

if (brokenCountAt[nextRow][nextCol] != -1) continue // 한번 방문한 곳은 재방문X

if (maze[nextRow][nextCol] == 0) {
    brokenCountAt[nextRow][nextCol] = brokenCountAt[row][col]
    deque.addFirst(Pair(nextRow, nextCol))
} else {
    brokenCountAt[nextRow][nextCol] = brokenCountAt[row][col] + 1
    deque.addLast(Pair(nextRow, nextCol))
}

 

여기서도, 가중치에 따라 이동 방향의 우선순위를 결정하기 때문에 DFS 기반으로 탐색을 하기엔 어렵습니다.  

 

생각 과정

1. 특정 위치로 가는 그래프 탐색 문젠데, 최단거리가 아니라 최소 가중치 문제이다
2. 노드를 한번씩만 방문하면 이동방향에 따라 최소 가중치 경로를 찾지 못할 수도 있다
3. 최소 가중치 경로를 찾을수 있도록 조건에 따라 재탐색을 허용한다.
4. 아니면 처음부터 최소 가중치로 탐색하면서 한번씩만 방문할 순 없을까 고민해본다.
5. 다익스트라를 알고 있다면 다익스트라나 우선순위 큐를 떠올릴 수 있다.

 

코드1 (BFS사용, 조건에 따라 재탐색 허용)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine())
    val colSize = st.nextToken().toInt()
    val rowSize = st.nextToken().toInt()
    val maze = Array(rowSize) {
        readLine().toCharArray()
    }

    print(getMinCount(maze))
}

fun getMinCount(maze: Array<CharArray>): Int {
    val dRow = intArrayOf(-1, 1, 0, 0)
    val dCol = intArrayOf(-0, 0, -1, 1)
    
    // 경로를 지나면서 벽을 몇 개 부셨는지 기록,
    // 큰 값으로 초기화해서 처음 방문할 때는 항상 방문하면서 갱신하게 한다
    val brokenCountAt = Array(maze.size) {
        IntArray(maze[0].size) { 10_000 }
    }
    val q: Queue<Pair<Int, Int>> = LinkedList()
    q.add(Pair(0, 0))
    brokenCountAt[0][0] = 0

    while (q.isNotEmpty()) {
        val (row, col) = q.poll()

        for (i in 0 until 4) {
            val nextRow = row + dRow[i]
            val nextCol = col + dCol[i]

            if (nextRow !in maze.indices || nextCol !in maze[0].indices) continue

            // 벽을 부셔야하는 상황에서 기존에 기록된 경로 값이 지금의 경로 값이 값보다 크다면 재탐색한다
            if (maze[nextRow][nextCol] == '1' && brokenCountAt[nextRow][nextCol] > brokenCountAt[row][col] + 1) {
                brokenCountAt[nextRow][nextCol] = brokenCountAt[row][col] + 1
                q.add(Pair(nextRow, nextCol))
            }
            // 벽을 부시지 않아도 되지만, 기존 경로 값이 지금 경로 값보다 크면 재탐색
            else if (maze[nextRow][nextCol] == '0' && brokenCountAt[nextRow][nextCol] > brokenCountAt[row][col]) {
                brokenCountAt[nextRow][nextCol] = brokenCountAt[row][col]
                q.add(Pair(nextRow, nextCol))
            }
        }
    }

    return brokenCountAt[maze.lastIndex][maze[0].lastIndex]
}

 

코드2 (낮은 가중치 우선 탐색)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

// anima94님 풀이 참고 
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (colSize, rowSize) = readLine().split(" ").map(String::toInt)
    val maze = Array<IntArray>(rowSize) {
        val string = readLine()
        IntArray(colSize) { i ->
            string[i] - '0'
        }
    }
    
    // 벽을 부순 횟수를 기록 + 방문 여부 표시 역할
    val brokenCountAt = Array<IntArray>(rowSize) {
        IntArray(colSize) { -1 }
    }
    val deque = ArrayDeque<Pair<Int, Int>>()
    val dRow = intArrayOf(-1, 1, 0, 0)
    val dCol = intArrayOf(0, 0, -1, 1)

    brokenCountAt[0][0] = 0
    deque.add(Pair(0, 0))

    while (true) {
        val (row, col) = deque.pollFirst()

        if (row == rowSize - 1 && col == colSize - 1) {
            print(brokenCountAt[row][col])
            return
        }

        for (i in 0 until 4) {
            val nextRow = row + dRow[i]
            val nextCol = col + dCol[i]

            if (nextRow !in 0 until rowSize || nextCol !in 0 until colSize) continue
            if (brokenCountAt[nextRow][nextCol] != -1) continue // 한번 방문한 곳은 재방문X

            if (maze[nextRow][nextCol] == 0) {
                brokenCountAt[nextRow][nextCol] = brokenCountAt[row][col]
                deque.addFirst(Pair(nextRow, nextCol))
            } else {
                brokenCountAt[nextRow][nextCol] = brokenCountAt[row][col] + 1
                deque.addLast(Pair(nextRow, nextCol))
            }
        }
    }
}