주난의 난 - Swift 문제풀이
문제 링크
백준: 주난의 난
문제 분석
이 문제는 가중치가 같을 때 최단거리 탐색에 사용하는, 일반적인 bfs와는 조금 다르다.
왜냐하면 “0”을 만나면, 해당 queue를 계속 진행해야 하고 그 이외에는 다음 탐색 사이클에서, 새로운 시작점으로 저장해두어야 한다.
즉 queue가 두 개 필요하다.
메인 큐: 현재 탐색하고자 하는 위치 담은 큐 배열. 만약 0이 있으면 그 다음 위치도 계속 탐색하게 됨.
temp 큐: 다음 사이클에서 메인 큐 시작점들 담은 배열 (이번 점프에서 쓰러트린 친구들의 위치를 담았다고 볼 수 있다.)
그리고 y, x 좌표를 일차원 배열로 큐에 담기 위해 모듈러 연산을 했다. (ex: 3004 -> y: 3, x: 4)
내 코드
import Foundation
func solve() {
let dy = [-1, 0, 1, 0] // 상하좌우 방향벡터
let dx = [0, 1, 0, -1]
// 입력 처리
let input = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (input[0], input[1])
let input2 = readLine()!.split(separator: " ").map { Int($0)! }
let (y1, x1, y2, x2) = (input2[0] - 1, input2[1] - 1,
input2[2] - 1, input2[3] - 1) // 1-based → 0-based
// 맵 입력 (Character 배열로 처리)
var arr: [[Character]] = []
for _ in 0..<n {
let line = Array(readLine()!) // "1#10111" → ['1','#','1','0','1','1','1']
arr.append(line)
}
// bfs 초기화
var queue: [Int] = [1000 * y1 + x1] // 좌표 (y, x) -> y * 1000 + x
var queueIndex = 0
// 방문 처리 및 각 지점에 점프 횟수 기록 배열
var visited = Array(repeating: Array(repeating: 0, count: m), count: n)
visited[y1][x1] = 1
var jump = 0
// 범인 위치가 쓰러질 까지
while true {
if arr[y2][x2] == "0" {
break
}
jump += 1
// 다음 점프를 위한 큐
var temp: [Int] = []
let startPoints = queue.map { "(\($0 / 1000), \($0 % 1000))" }.joined(separator: ", ")
print("\(jump)번째 점프! 시작점들: [\(startPoints)]")
// 현재 점프 전파하기 (쓰러트리기)
while queueIndex < queue.count {
let cur = queue[queueIndex]
let y = cur / 1000
let x = cur % 1000
queueIndex += 1
print("현재 위치(queue): \(y), \(x)")
for i in 0..<4 {
let ny = y + dy[i]
let nx = x + dx[i]
print("다음 위치: \(ny), \(nx)")
// 오버플로우 체크, 방문 체크
if ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx] != 0 { continue }
// 방문 처리 (점프 횟수 기록)
visited[ny][nx] = jump
// 만약 친구(1), 범인(#)라면
if arr[ny][nx] != "0" {
print("친구를 쓰러트림!, temp에 해당 친구 위치 저장!", arr[ny][nx], ny, nx)
// 쓰러트리기
arr[ny][nx] = "0"
// 다음 점프 시작점으로 temp queue에 저장
temp.append(1000 * ny + nx)
} else {
// 만약 빈 공간이라면, 같은 점프에서 계속 진행
print("빈 공간이므로, 계속 탐색 진행", arr[ny][nx], ny, nx)
queue.append(1000 * ny + nx)
}
}
}
print("현재 queue를 다 돌았음!")
// 친구들을 쓰러트린 위치들(temp)이 다음 시작점이므로 메인 큐로 교체
queue = temp
queueIndex = 0
}
}
solve()시간 복잡도
전체 맵의 크기가 n, m 일 때 O(n * m * 점프횟수)
출력
5 7
3 4 1 2
1#10111
1101001
001*111
1101111
0011001
1번째 점프! 시작점들: [(2, 3)]
현재 위치(queue): 2, 3
다음 위치: 1, 3
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 1 3
다음 위치: 2, 4
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 2 4
다음 위치: 3, 3
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 3 3
다음 위치: 2, 2
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 2 2
현재 queue를 다 돌았음!
2번째 점프! 시작점들: [(1, 3), (2, 4), (3, 3), (2, 2)]
현재 위치(queue): 1, 3
다음 위치: 0, 3
빈 공간이므로, 계속 탐색 진행 0 0 3
다음 위치: 1, 4
빈 공간이므로, 계속 탐색 진행 0 1 4
다음 위치: 2, 3
다음 위치: 1, 2
빈 공간이므로, 계속 탐색 진행 0 1 2
현재 위치(queue): 2, 4
다음 위치: 1, 4
다음 위치: 2, 5
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 2 5
다음 위치: 3, 4
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 3 4
다음 위치: 2, 3
현재 위치(queue): 3, 3
다음 위치: 2, 3
다음 위치: 3, 4
다음 위치: 4, 3
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 4 3
다음 위치: 3, 2
빈 공간이므로, 계속 탐색 진행 0 3 2
현재 위치(queue): 2, 2
다음 위치: 1, 2
다음 위치: 2, 3
다음 위치: 3, 2
다음 위치: 2, 1
빈 공간이므로, 계속 탐색 진행 0 2 1
현재 위치(queue): 0, 3
다음 위치: -1, 3
다음 위치: 0, 4
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 0 4
다음 위치: 1, 3
다음 위치: 0, 2
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 0 2
현재 위치(queue): 1, 4
다음 위치: 0, 4
다음 위치: 1, 5
빈 공간이므로, 계속 탐색 진행 0 1 5
다음 위치: 2, 4
다음 위치: 1, 3
현재 위치(queue): 1, 2
다음 위치: 0, 2
다음 위치: 1, 3
다음 위치: 2, 2
다음 위치: 1, 1
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 1 1
현재 위치(queue): 3, 2
다음 위치: 2, 2
다음 위치: 3, 3
다음 위치: 4, 2
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 4 2
다음 위치: 3, 1
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 3 1
현재 위치(queue): 2, 1
다음 위치: 1, 1
다음 위치: 2, 2
다음 위치: 3, 1
다음 위치: 2, 0
빈 공간이므로, 계속 탐색 진행 0 2 0
현재 위치(queue): 1, 5
다음 위치: 0, 5
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 0 5
다음 위치: 1, 6
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 1 6
다음 위치: 2, 5
다음 위치: 1, 4
현재 위치(queue): 2, 0
다음 위치: 1, 0
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 1 0
다음 위치: 2, 1
다음 위치: 3, 0
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 3 0
다음 위치: 2, -1
현재 queue를 다 돌았음!
3번째 점프! 시작점들: [(2, 5), (3, 4), (4, 3), (0, 4), (0, 2), (1, 1), (4, 2), (3, 1), (0, 5), (1, 6), (1, 0), (3, 0)]
현재 위치(queue): 2, 5
다음 위치: 1, 5
다음 위치: 2, 6
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 2 6
다음 위치: 3, 5
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 3 5
다음 위치: 2, 4
현재 위치(queue): 3, 4
다음 위치: 2, 4
다음 위치: 3, 5
다음 위치: 4, 4
빈 공간이므로, 계속 탐색 진행 0 4 4
다음 위치: 3, 3
현재 위치(queue): 4, 3
다음 위치: 3, 3
다음 위치: 4, 4
다음 위치: 5, 3
다음 위치: 4, 2
현재 위치(queue): 0, 4
다음 위치: -1, 4
다음 위치: 0, 5
다음 위치: 1, 4
다음 위치: 0, 3
현재 위치(queue): 0, 2
다음 위치: -1, 2
다음 위치: 0, 3
다음 위치: 1, 2
다음 위치: 0, 1
친구를 쓰러트림!, temp에 해당 친구 위치 저장! # 0 1
현재 위치(queue): 1, 1
다음 위치: 0, 1
다음 위치: 1, 2
다음 위치: 2, 1
다음 위치: 1, 0
현재 위치(queue): 4, 2
다음 위치: 3, 2
다음 위치: 4, 3
다음 위치: 5, 2
다음 위치: 4, 1
빈 공간이므로, 계속 탐색 진행 0 4 1
현재 위치(queue): 3, 1
다음 위치: 2, 1
다음 위치: 3, 2
다음 위치: 4, 1
다음 위치: 3, 0
현재 위치(queue): 0, 5
다음 위치: -1, 5
다음 위치: 0, 6
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 0 6
다음 위치: 1, 5
다음 위치: 0, 4
현재 위치(queue): 1, 6
다음 위치: 0, 6
다음 위치: 1, 7
다음 위치: 2, 6
다음 위치: 1, 5
현재 위치(queue): 1, 0
다음 위치: 0, 0
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 0 0
다음 위치: 1, 1
다음 위치: 2, 0
다음 위치: 1, -1
현재 위치(queue): 3, 0
다음 위치: 2, 0
다음 위치: 3, 1
다음 위치: 4, 0
빈 공간이므로, 계속 탐색 진행 0 4 0
다음 위치: 3, -1
현재 위치(queue): 4, 4
다음 위치: 3, 4
다음 위치: 4, 5
빈 공간이므로, 계속 탐색 진행 0 4 5
다음 위치: 5, 4
다음 위치: 4, 3
현재 위치(queue): 4, 1
다음 위치: 3, 1
다음 위치: 4, 2
다음 위치: 5, 1
다음 위치: 4, 0
현재 위치(queue): 4, 0
다음 위치: 3, 0
다음 위치: 4, 1
다음 위치: 5, 0
다음 위치: 4, -1
현재 위치(queue): 4, 5
다음 위치: 3, 5
다음 위치: 4, 6
친구를 쓰러트림!, temp에 해당 친구 위치 저장! 1 4 6
다음 위치: 5, 5
다음 위치: 4, 4
현재 queue를 다 돌았음!