반응형
문제 풀이:
빌딩이 정육면체이므로 동서남북상하로 BFS를 돌려서 이동하는 시간을 구해야 한다.
BFS를 쓸 줄 안다면 쉽게 해결할 수 있는 문제이다.
코드:
typealias Coord = (l: Int, r: Int, c: Int)
let d: [Coord] = [(-1,0,0), (1,0,0), (0,-1,0), (0,1,0), (0,0,-1), (0,0,1)]
func bfs(
_ start: Coord,
_ exit: Coord,
_ check: inout [[[Int]]],
_ building: [[[String]]],
_ b: Coord
) {
var q = [Coord]()
q.append(start)
check[start.l][start.r][start.c] = 1
var index = 0
while index < q.count {
let now = q[index]
index += 1
// 동서남북상하
for i in 0 ..< 6 {
let nl = now.l + d[i].l
let nr = now.r + d[i].r
let nc = now.c + d[i].c
guard 0 <= nl && nl < b.l &&
0 <= nr && nr < b.r &&
0 <= nc && nc < b.c
else { continue }
if check[nl][nr][nc] == 0 {
// "." 또는 "E"일 때 큐에 넣고 이동하는 시간을 늘림
if building[nl][nr][nc] == "." || building[nl][nr][nc] == "E" {
q.append((nl,nr,nc))
check[nl][nr][nc] = check[now.l][now.r][now.c] + 1
}
}
}
}
}
func solution() {
while true {
let lrc = readLine()!.split(separator: " ").map { Int(String($0))! }
let l = lrc[0]
let r = lrc[1]
let c = lrc[2]
let border: Coord = (l,r,c)
// 반복문 종료조건
if l == 0 && r == 0 && c == 0 {
break
}
var building = [[[String]]](
repeating: [[String]](
repeating: [String](),
count: r
),
count: l
)
var check = [[[Int]]](
repeating: [[Int]](
repeating: [Int](
repeating: 0,
count: c
),
count: r
),
count: l
)
var start: Coord = (0,0,0)
var exit: Coord = (0,0,0)
// Input
for i in 0 ..< l {
for j in 0 ..< r {
let input = Array(readLine()!).map { String($0) }
building[i][j].append(contentsOf: input)
}
_ = readLine()!
}
// 시작과 출구 좌표 저장
for i in 0 ..< l {
for j in 0 ..< r {
for k in 0 ..< c {
if building[i][j][k] == "S" {
start = (i,j,k)
} else if building[i][j][k] == "E" {
exit = (i,j,k)
}
}
}
}
bfs(start, exit, &check, building, border)
let res = check[exit.l][exit.r][exit.c]
// 출구의 좌표를 이용해서 이동한 시간이 0이면 Trapped
if res == 0 {
print("Trapped!")
} else {
print("Escaped in \(res - 1) minute(s).")
}
}
}
solution()
문제:
반응형
'Algorithm > BOJ' 카테고리의 다른 글
[Algorithm/BOJ] 2910 - 빈도 정렬 Swift (3) | 2021.07.01 |
---|---|
[Algorithm/BOJ] 9466 - 텀 프로젝트 Swift (0) | 2021.06.17 |
[Algorithm/BOJ] 1431 - 시리얼 번호 Swift Python (0) | 2021.06.03 |
[Algorithm/BOJ] 14500 - 테트로미노 Swift Python (0) | 2021.06.02 |
[Algorithm/BOJ] 4889 - 안정적인 문자열 Swift Python (0) | 2021.05.21 |
댓글