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

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 2178 미로 탐색" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

2178번: 미로 탐색

 

---

풀이

이번 문제는 bfs 문제입니다.

dfs로 풀 수 없는 이유는 "최소" 길이를 구해야 하기 때문입니다.

dfs는 끝까지 가는 루트가 최소를 보장하지 않기 때문에 bfs로 해결을 해야합니다.

 

input에서 유의해야 할 점은 높이가 먼저 입력이 된다는 점입니다.

편견이지만 보통은 w, h 순서로 input을 하는데 이번 문제는 h, w 순서라 한 번 틀렸네요.. 문제를 제대로 읽읍시다.

 

queue는 x, y, count가 담긴 tuple 배열로 선언했고 (0, 0, 1)로 초기화하였습니다.

count가 1로 초기화한 이유는 문제에 시작과 끝도 카운트를 한다고 하였기 때문입니다.

 

이후 index를 이용해 queue를 참조하며 상하좌우를 살핍니다.

상하좌우 중 값이 1인 좌표가 있다면 queue에 좌표와 count + 1을 하여 push 합니다.

 

nx, ny가 h, w와 동일하다면 break하고 결과를 출력하면 됩니다. 

 

---

전체 코드

//2178 미로 탐색
import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let h = input[0], w = input[1]
var result = 0

var graph: [[Int]] = []
for _ in 0..<h {
    let input = readLine()!.map { Int(String($0))! }
    graph.append(input)
}

var queue: [(x: Int, y: Int, count: Int)] = [(0,0,1)]
var index = 0

let dx: [Int] = [1, -1, 0, 0]
let dy: [Int] = [0, 0, -1, 1]
while index < queue.count {
    let node = queue[index]
    index += 1
    
    for i in 0..<4 {
        let nx = node.x + dx[i]
        let ny = node.y + dy[i]
        let nCount = node.count + 1
        
        if nx >= 0 && nx < h && ny >= 0 && ny < w {
            if graph[nx][ny] == 1 {
                result = nCount
                if nx == h-1 && ny == w-1 {
                    index = queue.count
                    break
                }
                
                graph[nx][ny] = 0
                queue.append((nx, ny, nCount))
            }
        }
    }
}

print(result)

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.