[백준 2178번][Kotlin] 미로 탐색

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

2178번: 미로 탐색

 

난이도 : 실버 1
태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색

 

 

설명

DFS와 BFS

그래프 탐색 문제이며, DFS와 BFS를 통해 구할 수 있습니다.

그러나, 이 문제에서는 BFS가 보다 적합합니다.

 

DFS의 경우 모든 경로를 확인하며, 그중에서 가장 짧은 경로를 선택하여야 합니다.

BFS의 경우는, 처음 마지막 좌표에 도착한 시점의 경로가 가장 짧은 경로입니다.

 

따라서 단순히 그래프를 탐색하는 것이 목적일때는 DFS/BFS 어느것을 사용해도 무방하나,

이와 같은 최단경로 문제의 경우는 BFS가 적합합니다.

 

 

 

소스코드

인풋값 저장

val br = BufferedReader(InputStreamReader(System.`in`))
val nm = br.readLine().split(" ")
val n = nm[0].toInt()
val m = nm[1].toInt()

val map = Array(n) { Array(m) { 0 } }

repeat(n) { x ->
    val line = br.readLine()
    repeat(m) { y ->
        map[x][y] = line[y] - '0'
    }
}

BufferedReader를 사용하여 입력을 받고,  배열에 저장하였습니다.

 

 

좌표를 담을 클래스와 방향을 담을 변수 생성

data class Node(val x: Int, val y: Int)

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

좌표를 담을 클래스 Node(x,y)를 만들고,

이동할 방향을 정하는데 도움을 줄 dx와 dy 배열을 만들었습니다.

 

 

최단 경로 찾기 (BFS)

val q: Queue<Node> = LinkedList()
val visited = Array(n) { Array(m) { 1 } }

q.offer(Node(0, 0))
visited[0][0] = 1

 

bfs에 사용할 q를 선언하고 0,0 좌표를 큐에 넣습니다.

방문여부를 담을 visited를 선언합니다.

 

다만, 다른 그래프 탐색처럼 true/false의 boolean형이 아닌, Int 형을 사용하였습니다.

최단 경로를 구하는 것이 목적이기 때문에 해당 좌표까지의 최단거리를 저장하는데 사용하기 위함입니다.

 

 

while (q.isNotEmpty()) {
    val target = q.poll()

    for (i in 0 until 4) {
        val nx = target.x + dx[i]
        val ny = target.y + dy[i]

        if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] == 0 || visited[nx][ny] != 1)
            continue

        q.offer(Node(nx, ny))
        visited[nx][ny] = visited[target.x][target.y] + 1

        if (nx == n - 1 && ny == m - 1) {
            println(visited[nx][ny])
            break
        }
    }
}

q에서 하나씩 원소를 빼며 반복문을 진행합니다.

 

이후 4번(상하좌우)의 반복문을 돌립니다.

 

 

if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] == 0 || visited[nx][ny] != 1)
    continue

만약 새 좌표(nx, ny)가 맵 범위를 벗어날 경우, 방문이 불가능할 경우(0, 벽), 이미 방문한 좌표의 경우(visited[nx][ny] != 1)

다음 회차로 넘어갑니다.

 

 

q.offer(Node(nx, ny))
visited[nx][ny] = visited[target.x][target.y] + 1

그렇지 않다면 해당 좌표를 큐에 집어넣고, 방문처리합니다.

이때, 해당 좌표까지의 거리를 visited에 저장합니다.

 

if (nx == n - 1 && ny == m - 1) {
    println(visited[nx][ny])
    break
}

만약 목표 좌표에 도달했다면, 반복문을 끝내고 해당 좌표까지의 거리를 출력합니다.

bfs의 경우 해당 좌표를 처음 방문했을 때, 그 좌표까지의 거리가 최단경로 입니다.

 

 

전체 소스코드

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

data class Node(val x: Int, val y: Int)

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val nm = br.readLine().split(" ")
    val n = nm[0].toInt()
    val m = nm[1].toInt()

    val map = Array(n) { Array(m) { 0 } }

    repeat(n) { x ->
        val line = br.readLine()
        repeat(m) { y ->
            map[x][y] = line[y] - '0'
        }
    }

    bfs(n, m, map)
}

fun bfs(n: Int, m: Int, map: Array<Array<Int>>) {
    // 1 - 이동가능, 0 - 벽
    val q: Queue<Node> = LinkedList()
    val visited = Array(n) { Array(m) { 1 } }

    q.offer(Node(0, 0))
    visited[0][0] = 1

    while (q.isNotEmpty()) {
        val target = q.poll()

        for (i in 0 until 4) {
            val nx = target.x + dx[i]
            val ny = target.y + dy[i]

            if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] == 0 || visited[nx][ny] != 1)
                continue

            q.offer(Node(nx, ny))
            visited[nx][ny] = visited[target.x][target.y] + 1

            if (nx == n - 1 && ny == m - 1) {
                println(visited[nx][ny])
                break
            }
        }
    }
}

 

 

 

후기

BFS를 사용한 그래프 탐색 / 최단경로 문제입니다.

최단경로 문제의 경우, 매 상황마다 최단경로 값을 저장하기에 다이나믹 프로그래밍으로 분류되기도 하는데,

 

위 소스코드도 visited에 매 상황마다 최단경로를 저장하기에 일종의 다이나믹 프로그래밍으로도 볼 수 있을 것 같습니다.