https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
골드 난이도의 BFS문제를 여러 개 풀어보면서 느끼는 공통점은 기본적으로 3차원 배열을 통해 문제를 풀어야 한다는 점이다.
풀이
크게 3가지 케이스로 나누어 경로탐색을 진행해야 한다.
- 벽을 아직 부수지 않은 상태에서 길을 만났을 경우
- 벽을 아직 부수지 않은 상태에서 벽을 만났을 경우
- 이미 벽을 부순상태에서 길을 만났을 경우
경로를 확인하는 visited 배열은 지난번 [1600] 말이 되고픈 원숭이 문제와 같다. 지난번에는 말의 움직임을 몇 번 사용했는지를 확인했다면, 이번에는 벽을 부쉈는지(1), 부수지 않았는지(0) 두 가지만 판별하면 되므로 visited[x][y][2]의 형태로 선언하면 된다.
정답 코드
import Foundation
let nm = readLine()!.split(separator: " ").map{Int($0)!}
let n = nm[0]
let m = nm[1]
var map = Array(repeating: [Int](), count: n)
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 2), count: m), count: n)
for i in 0..<n{
map[i] = readLine()!.map{Int(String($0))!}
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
var ans = -1
func bfs(){
var q = [[0,0,0,1]]
var dq = [[Int]]()
visited[0][0][0] = true
while !q.isEmpty{
dq = q.reversed()
q.removeAll()
for _ in 0..<dq.count{
let curr = dq.removeLast()
let x = curr[0]
let y = curr[1]
let wall = curr[2]
let cnt = curr[3]
if x==n-1 && y==m-1{
ans = cnt
return
}
for i in 0..<4{
let nx = x + dx[i]
let ny = y + dy[i]
if nx<0 || nx>=n || ny<0 || ny>=m {continue}
if wall==0 && map[nx][ny]==0 && !visited[nx][ny][0]{
visited[nx][ny][0] = true
q.append([nx,ny,0,cnt+1])
}
if wall==0 && map[nx][ny]==1 && !visited[nx][ny][1]{
visited[nx][ny][1] = true
q.append([nx,ny,1,cnt+1])
}
if wall==1 && map[nx][ny]==0 && !visited[nx][ny][1]{
visited[nx][ny][1] = true
q.append([nx,ny,wall,cnt+1])
}
}
}
}
}
bfs()
print(ans)
'Problem Solving > BOJ' 카테고리의 다른 글
| [2146] 다리 만들기 (2) | 2022.10.13 |
|---|---|
| [17071] 숨바꼭질 5 (0) | 2022.10.12 |
| [1600] 말이 되고픈 원숭이 (2) | 2022.10.05 |
| [4179] 불! (0) | 2022.09.29 |
| [2294] 동전 2 (0) | 2022.09.22 |
