백준 18818 Iguana Instructions Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/18818

18818번: Iguana Instructions

문제

Iggy the Iguana has found himself trapped in a corn maze! The corn maze can be modelled as a square grid where some of the cells are blocked off with impassable corn plants and others are cleared out. Iggy can only travel in and through cells that are cleared out. Iggy can move to a cell in any of the four cardinal directions (north, south, east, and west).

Iggy is not good at mazes and needs your help. He has asked you to write down a list of instructions to show him how to reach the end of the maze. Each instruction has the form <direction> <amount> where <direction> is either North, South, East, or West and <amount> is how many cells Iggy should travel in that direction. Because Iggy has a bad memory, he wants this list of instructions to be as short as possible even if that means he has to walk further.

Iggy starts in the top-left cell of the maze and needs to get to the bottom-right cell. It is guaranteed that there exists a path Iggy can take to reach the end.

What is the minimum number of instructions you can give Iggy so that he can reach the end of the maze?

입력

The first line contains n (2 ≤ n ≤ 100), which is the length of one side of the square grid representing the maze.

Following this is an n × n grid of characters. If a cell is cleared out, its corresponding character is a dot (.). If a cell is blocked off with corn plants, its corresponding character is a hash (#).

출력

Display the minimum number of instructions you can give Iggy such that he can reach the end of the maze.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

간단한 bfs 문제이다.

방향을 기준으로 이구아나한테 명령을 내리는데 가장 적은 명령 횟수로 목적지에 도달해야 한다.

즉, 목적지에 방향을 최소한으로 바꾸고 도착했을 때 그 변경된 방향의 수가 정답이다.

일반적인 bfs로 풀려면 방향에 따른 visited값을 따로 두어야 한다.

그리고 visited에는 Boolean값이 아닌, Int를 저장한다.

// visited[dir][r][c] = r,c에 dir방향으로 도착했을 때 방향 전환 최솟값

r,c 칸에 방향 전환 3번 하고 방문했다고 하자.

이후 r,c칸에 방향 전환 2번 하고 방문하는 일이 있을 수 있기 때문에

해당 칸에 같은 방향으로 방문했을 때 방향 전환을 더 조금 하고 도착한 경우는 탐색을 이어나간다. 

만약 방향을 구분하지 않고 visited[r][c]에 최솟값만 저장한다면,

visited[r][c] = 3, 방향은 우측

visited[r][c] = 3, 방향은 좌측
두 가지 경우가 답이 다르게 나올 수 있기 때문에

탐색의 가지치기에서

if(visited[dir][r][c] <= cnt) continue 가 아닌 

if(visited[r][c] < cnt) continue가 된다. (같은 방향 전환 횟수로 방문했을 때 방향이 다를 수 있으므로 탐색을 이어가야 한다는 뜻)

하지만 후자의 경우 탐색의 가지가 더 많아진다.

 

여기까지가 내가 제출한 풀이이고,

다른 풀이도 있다.

문제에선 방향 전환 횟수를 요구하므로 어떠한 좌표에서 탐색을 시작할 때, 이동할 수 있는 끝까지 이동하면서 큐에 삽입하는 방식으로 푼다면 단순히 visited[r][c] = true/false를 사용할 수 있고, 본래 Bfs 성질처럼 가장 먼저 목적지에 도착하는 경우의 방향 전환 횟수가 답이 된다. 그러므로 가장 적은 탐색으로 답을 찾을 수 있다.

 

 

 

코드

import java.util.*
val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()


data class Node(
    val r: Int,
    val c: Int,
    val dir: Int,
    val cnt: Int
)

lateinit var graph: Array<String>
lateinit var visited: Array<Array<IntArray>>
val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(-1, 0)
)

fun bfs(n: Int): Int {
    var answer = Int.MAX_VALUE
    val q: Queue<Node> = LinkedList()
    q.add(Node(0, 0, -1, 0))

    //방향이 바뀐 수 카운트
    while (q.isNotEmpty()) {
        val cur = q.poll()
        for (i in 0 until 4) {
            val nr = cur.r + dir[i][0]
            val nc = cur.c + dir[i][1]
            if (nr !in 0 until n || nc !in 0 until n) continue
            if (graph[nr][nc] == '#') continue
            val nCnt = if (cur.dir != i) cur.cnt + 1 else cur.cnt
            if(nr == n-1 && nc == n-1){
                answer = answer.coerceAtMost(nCnt)
                continue
            }
            if (visited[i][nr][nc] <=nCnt) continue
            q.add(Node(nr, nc, i, nCnt))
            visited[i][nr][nc] = nCnt
        }
    }
    return answer
}

fun main() = with(System.out.bufferedWriter()) {

    //input
    val n = getInt()
    graph = Array(n) { br.readLine() }
    visited = Array(4) { Array(n) { IntArray(n){Int.MAX_VALUE} } }

    //solve,output
    write("${bfs(n)}")
    close()
}