백준 - 2206 벽 부수고 이동하기 풀이

문제

2206 벽 부수고 이동하기

풀이

1. 알고 있어야 할 점

• 이 문제는 너비 우선 탐색(bfs)을 이용하여 푸는 문제이다.
• 가중치가 모두 동일한 최단거리 문제는 대부분 너비 우선 탐색으로 풀 수 있다.
  • 가중치가 있는 경우 다익스트라 알고리즘 등으로 풀 수 있다.
• 일반적인 너비 우선 탐색 문제와 차이는 벽을 1번 부술 수 있다는 점이다.

Step by Step

1. 초기화

• 입력된 맵을 배열로 선언한다.
• 큐를 생성하고, 시작 노드의 정보를 입력한다.
  • 들어가야 할 정보는 노드의 좌표, 현재까지 지나온 거리, 벽을 부수었는지 여부 이다.
• 각 경로의 방문 여부(지나 왔는지 여부) 저장할 공간을 선언한다.
  • 방문 여부는 벽을 부수고 방문과 벽을 부수지 않고 방문하였는지를 각각 저장한다.

2. BFS 수행

• 큐에 값이 있으면 계속 수행되는 반복문을 선언한다.
• 큐에서 노드를 하나 꺼낸다.
• 해당 노드의 좌표가 맵의 마지막(목적지)이면 노드의 거리를 출력하고 프로그램을 종료한다.
• 해당 노드의 좌표가 맵의 범위를 벗어났으면 2를 처음부터 반복한다.
• 해당 노드가 이미 벽을 부수었고, 현재 위치가 벽이면 2를 처음부터 반복한다.
• 해당 노드가 이미 방문 한 곳인지 확인하고, 방문한 곳이면 2를 처음부터 반복한다.
• 해당 노드의 상하좌우 인접한 노드를 큐에 저장한다.
  • 해당 노드가 이미 벽을 부수었더나, 현재 위치가 벽이면 벽을 부수었다고 표시한다.

3. 종료

• 2에서 큐가 비어서 반복문이 종료되었다면 -1을 출력하고 프로그램을 종료한다.

답

kotlin code

fun main() {
    val map: Array<BooleanArray> = readMap()
    val shortestDistance: Int = getShortestDistance(map)
    println(shortestDistance)
}

private fun readMap(): Array<BooleanArray> = Array(readln().split(' ').first().toInt()) { readln().toCharArray().map { it == '1' }.toBooleanArray() }

private fun getShortestDistance(map: Array<BooleanArray>): Int {
    val queue: java.util.Queue<Node> = java.util.LinkedList<Node>().apply {
        this.offer(Node(0, 0, 1, false))
    }
    val xDirection = arrayOf(1, -1, 0, 0)
    val yDirection = arrayOf(0, 0, 1, -1)

    val visited = Array(2) { Array(map.size) { BooleanArray(map.first().size) { false } } }

    while (queue.isNotEmpty()) {
        val node = queue.poll()
        if(node.isEndOfMap(map)) return node.distance
        
        if(node.isOutOfRangeOfMap(map)) continue
        if(node.isDuplicateBreak(map)) continue
        if(node.isDuplicateVisit(visited)) continue

        visited[node.didBreakWall.toInt()][node.y][node.x] = true

        for(i in 0..3)
            queue.offer(node.getNext(xDirection[i], yDirection[i], map))
    }
    return -1
}

data class Node(val x: Int, val y: Int, val distance: Int, val didBreakWall: Boolean) {
    fun getNext(xDirection: Int, yDirection: Int, map: Array<BooleanArray>) = Node(x + xDirection, y + yDirection,distance + 1, didBreakWall || map[y][x])
    fun isOutOfRangeOfMap(map: Array<BooleanArray>) = x !in (0..map.first().lastIndex) || y !in (0..map.lastIndex)
    fun isEndOfMap(map: Array<BooleanArray>) = x == map.first().lastIndex && y == map.lastIndex
    fun isDuplicateBreak(map: Array<BooleanArray>) = didBreakWall && map[y][x]
    fun isDuplicateVisit(visited: Array<Array<BooleanArray>>) = visited[didBreakWall.toInt()][y][x]
}

private fun Boolean.toInt() = if(this) 1 else 0