[백준] 2178 미로 탐색 [Swift]

문제 링크

2178번: 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

문제 풀이

이 문제에서 나타난 미로를 마치 가중치가 없는 무방향 그래프로 본다면 가중치가 없는 무방향 그래프에서 최단경로를 구할 때 사용하는 BFS(너비 우선 탐색)을 사용하면 될 것 같아요.

 

미로를 2차원 배열로 나타내면 어떠한 정점에서 이동할 수 있는 방향은 상, 하, 좌, 우가 됩니다.

BFS로 최단경로를 찾을 땐 어떤 정점을 방문했는지에 대한 정보, 어떤 정점을 방문하기 전에 방문한 정점에 대한 정보, 어떤 정점에 도달하기 위한 거리에 대한 정보가 필요합니다.

따라서 세 가지 정보를 저장하는 배열을 따로 만들어야 하는데요, 

어떤 정점을 방문했는지에 대한 정보는 모두 -1로 초기화 했고,

어떤 정점을 방문하기 전에 방문한 정점에 대한 정보는 [-1, -1]로 초기화했고,

어떤 정점에 도달하기 위한 거리에 대한 정보는 모두 0으로 초기화했습니다.

 

예를 들어 [0,0]을 시작점으로 BFS를 사용한다고 하면 첫 번째 탐색과정에서는 이러한 일들이 벌어집니다.

 

우선 [0,0]을 큐에서 꺼냅니다.

[0,0]에서 상하좌우로 이동할 수 있는 노드를 확인합니다.

[0,0]의 경우 [1,0], [0,1]로 이동할 수 있습니다.

이 정점들에 방문했는지 확인하고 방문하지 않았다면 큐에 추가합니다.

그리고 이 정점들의 방문 전 정점에 대한 정보를 [0,0]으로 초기화하고 도달하기 위한 거리를 [0,0] 정점에 도달하기 위한 거리에 1을 더한 값으로 초기화합니다.

이를 계속 반복합니다.

 

BFS를 마친 뒤 목표 정점에 도달하기 위한 거리에 대한 정보를 출력하면 이 문제의 답이 됩니다!

 

 

소스 코드

func solution() {
    let firstLine = readLine()!.split(separator: " ").map({Int($0)!})
    let n = firstLine[0]
    let m = firstLine[1]
    
    var maze = [[Int]]()
    
    for _ in 0..<n{
        maze.append(readLine()!.map({Int(String($0))!}))
    }
    
    // 방문한 노드인지 확인하는 배열
    var visited:[[Int]] = [[Int]](repeating: [Int](repeating: -1, count: m), count: n)
    // BFS에 필요한 큐
    var queue: [[Int]] = [[0,0]]
    
    let dx: [Int] = [0,0,-1,1] // 상하좌우
    let dy: [Int] = [-1,1,0,0] // 상하좌우
    
    // 시작점에서 어떤 노드에 도달하기 위한 바로 직전의 노드
    var predecessor: [[[Int]]] = [[[Int]]](repeating: [[Int]](repeating: [-1,-1], count: m), count: n)
    predecessor[0][0] = [0,0]
    
    // 시작점에서 어떤 노드에 도달하는 거리
    var distance: [[Int]] = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
    distance[0][0] = 1
    
    while queue.count != 0 {
        let now = queue.remove(at: 0)
        
        // 방문하지 않은 노드만 확인
        if visited[now[0]][now[1]] == -1 {
            visited[now[0]][now[1]] = 1
            for i in 0..<dx.count{
                let nowdx = now[0] - dx[i]
                let nowdy = now[1] - dy[i]
                
                if nowdx < 0 || nowdx > n-1 || nowdy < 0 || nowdy > m-1{
                    continue
                } else {
                    if maze[nowdx][nowdy] == 1 && visited[nowdx][nowdy] == -1{
                        predecessor[nowdx][nowdy] = now
                        distance[nowdx][nowdy] = distance[now[0]][now[1]] + 1
                        queue.append([nowdx,nowdy])
                    }
                }
            }
        }
    }
    print(distance[n-1][m-1])
}

solution()