[백준/Swift] 2178 미로 탐색

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2178 미로 탐색
• 제출 언어: Swift
• 알고리즘 분류:
  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색

---

풀이

BFS

모든 경로를 방문하는 것이 아니고 최단 거리를 찾는 문제이므로, 너비 우선 탐색으로 문제를 풀어야만 했다
그냥 BFS 문제처럼 방문해야 하는 노드를 넣는 queue를 하나 생성하고,
queue하나를 꺼낼 때마다 동서남북에 있는 노드들을 확인해서, 방문하지 않았고, 해당 숫자가 1이라 이동할 수 있는 칸일경우
그 칸을 또 queue에 넣는다.

이 때, 도착위치로 이동할 수 있는 최소한의 경로를 찾아야하므로, queue에서 꺼낸 값이 도착위치일 때, 해당 depth를 구하면 된다
depth를 구하기 위해 queue에 넣는 tuple내에 이전 노드의 count + 1한 값을 넣어준다

전체 코드

import Foundation
let n = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N,M) = (n[0], n[1])
var arr : [[Int]] = []
var visited = Array(repeating: Array(repeating: false, count: M), count: N)
for _ in 0..<N {
    arr.append(Array(readLine()!).map{Int(String($0))!})
}

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

// 깊이 탐색으로 하면 최단 거리를 구할 수 없으므로 너비 탐색으로 진행한다
        for i in 0...3 {
            let nx = target.x + dx[i]
            let ny = target.y + dy[i]

            // 그래프를 벗어날 경우 넘어간다
            if nx < 0 || ny < 0 || nx >= N || ny >= M {
                continue
            }
            // 아직 방문하지 않았고 이동할 수 있는 경우, queue에 넣고, arr값을 0로 한다 (다시 방문하지 않기 위해 표기)
            // count를 방문전 값에 +1 해준다
            if !visited[nx][ny] && arr[nx][ny] == 1 {
                arr[nx][ny] = 0
                queue.append((nx,ny, target.count+1))
            }
        }
    }
    return queue.count
}

print(BFS())