[Swift 알고리즘] 백준 2178 미로 탐색

×

BFS Silver 1

백준 2178 미로 탐색

문제
N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

가중치 없는 무방향 그래프에서 BFS로 최단 경로를 구하는 문제. 

왼쪽 형태의 미로를 오른쪽 최단경로 형태로 변환해주는 것이 포인트. 

머리로는 알겠다고 생각했는데 막상 구현을 하려니 너무너무 어려웠다. 

미로, 최단거리, 방문기록, 큐를 저장할 이차원배열을 이렇게 4개나 만들어줘야 한다. 고작 기본적인 BFS 문제일 뿐인데 머리가 아프다.. 

나 코딩에 소질이 없는걸까 🥲 머리가 나쁜걸까.. 어쩔 수 없지뭐..  많이 풀어보는 수 밖에.. 

 

풀이방법

69376KB 12ms

1. n, m, 미로 입력 받아오기

다음과 같이 입력받은 n, m 과 미로를 저장한다. 

저장된 미로 ex) [[1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1]]

let input = readLine()!.split(separator: " ").compactMap { Int($0) }
let n = input[0], m = input[1]

var maze = [[Int]]()
for _ in 0..<n {
    let input = readLine()!.compactMap { Int(String($0)) }
    maze.append(input)
}

2. 미로에서 상하좌우 탐색할 dx, dy 선언 

let dx = [0,0,-1,1]
let dy = [-1,1,0,0]

3. distance, visited 초기화

미로에서 방문 여부 저장하는 visited, 거리를 하나씩 더하며 최단거리를 저장할 distance 초기화 

var distance: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n)
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: m), count: n)

4. 큐를 이용하여 bfs로 최단경로 구하기

bfs 로 더 이상 queue에 값이 존재하지 않을 때까지 while문을 돌려서 최단거리를 구해준다. 

 1) 우선 시작점의 최단경로를 1로 설정해주고, visited = true로 바꿔준다. 

 2) (이미 방문했거나 갈 수 없는 곳을 제외하고) 탐색을 할 미로의 위치들을 넣어줄 큐를 시작점으로 초기화해준다.

 3) 큐에 더이상 남아있는 칸이 없을 때까지 탐색을 계속한다. 

  3-1) 탐색할 큐에서 제일 첫 번째 있는 항목을 dequeue하고 x, y 값으로 저장해준다. 

  3-2) x, y 의 상하좌우를 탐색하여, 해당 좌표로 이동가능하며 아직 방문하지 않은 위치일 경우 큐에 해당 좌표를 넣어준다.  

    distance 에서 해당 좌표 값을 +1 해주고, visited = true 로 변경하여 방문 기록을 남긴다.  

이렇게 해주면 저장된 최단경로 distance는 다음과 같이 저장된다.

ex) [[1, 0, 9, 10, 11, 12], [2, 0, 8, 0, 12, 0], [3, 0, 7, 0, 13, 14], [4, 5, 6, 0, 14, 15]]

func bfs() {
    distance[0][0] = 1
    visited[0][0] = true
    
    var queue: [[Int]] = [[0,0]]
    
    while !queue.isEmpty {
        let prev = queue.removeFirst()
        let x = prev[0]
        let y = prev[1]
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx >= 0 && nx < n && ny >= 0 && ny < m {
                if !visited[nx][ny] && maze[nx][ny] == 1 {
                    distance[nx][ny] = distance[x][y] + 1
                    visited[nx][ny] = true
                    queue.append([nx, ny])
                }
            }
        }
    }
}

5. 출력

distance에서 최종 도착 위치에 저장된 최단경로 값을 출력해주면 된다. 

bfs()
print(distance[n-1][m-1])

 

 

 

+ 방문 여부를 저장하는 visited와 최단경로 저장해줄 distance 를 따로 만들어주지 않고,

다음과 같이 원본 미로 내에서 좌표 값을 바로 최단거리로 바꾸어 가면서 풀어줄 수도 있다. 

//69240KB 12ms
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
let n = input[0], m = input[1]

var maze = [[Int]]()
for _ in 0..<n {
    let input = readLine()!.compactMap { Int(String($0)) }
    maze.append(input)
}

let dx = [0,0,-1,1], dy = [-1,1,0,0] //상하좌우

print(bfs())

func bfs() -> Int {
    var queue: [[Int]] = [[0,0]]
    
    while !queue.isEmpty {
        let prev = queue.removeFirst()
        let x = prev[0], y = prev[1]
        
        for i in 0..<4 {
            let nx = x + dx[i], ny = y + dy[i]
            
            if nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 1 {
                maze[nx][ny] = maze[x][y] + 1
                queue.append([nx, ny])
            }
        }
    }
    return maze[n-1][m-1]
}