그래프 탐색 문제다. 너비 우선 탐색으로 풀었다. 상어의 움직임에 대해 오래 고민했던 문제다.
풀이
상, 좌, 우, 하 순서로 너비 우선 탐색을 수행한다. 빈 곳이거나 같은 사이즈의 물고기를 만난다면 큐에 담아 이동을 수행, 자신보다 작은 사이즈의 물고기를 만나면 해당 좌표를 다른 배열에 저장하였다.
탐색이 끝난 뒤 문제의 조건에 맞게 먹을 수 있는 물고기가 담긴 배열을 시간, x좌표, y좌표 순으로 정렬한 뒤 가장 가까운 좌표로 이동하여 해당 물고기를 먹으면 된다. 처음에는 이러한 정렬 없이 먹을 수 있는 물고기를 만나면 바로 먹어버리고 탐색을 종료했는데, 같은 거리에 있는 먹을 수 있는 물고기에 대한 조건이 안 맞아 오답이 나왔다.
탐색 함수는 상어가 이동한 좌표와 걸린 시간을 반환하게 하였다. 상어의 좌표에 이동이 없는 경우 먹을 수 있는 물고기가 없는 것으로 판단하여 반목문을 빠져나오는 것으로 코드를 작성했다.
지도를 탐색하면서 인접 배열과의 인구수를 비교, 조건에 맞다면 큐에 담아낸 뒤 마지막에 큐에 담겨있는 좌표를 확인하면서 값을 갱신한다. 문제에서는 몇 차례의 변동이 일어났는지 횟수를 요구하기 때문에 반복문으로 수행한 뒤 Bool 타입의 flag 변수를 사용하여 종료 여부를 확인하였다.
정답에 닿을 듯 말듯해서 더욱 고생했던 문제다. 메모리 초과를 마주해서 고생하고, 이후 오답으로 인해 한번 더 고생했다.
풀이
문제를 보면 알겠지만 bfs를 두번 수행해야 한다. 본인도 거기까지는 생각했으나, 불의 경로와 지훈이의 경로를 어떻게 합칠 수 있을까에 대한 고민으로 시간을 소모했다. 항상 bfs문제를 만날 때면 Bool값을 통해 방문을 체크하는 visited 배열을 사용하는데, 이번 문제의 핵심은 해당 장소를 몇 초 후에 방문하는가를 저장하는 것이다. 불에 대한 경로탐색을 수행하고 나면 각 좌표에 몇 초 후에 불이 도달하는지 기록되어있다. 이후 지훈이의 경로탐색을 수행하여 불보다 먼저 해당 장소에 도착하는지를 확인하여 배열의 모서리까지 도달하면 된다.
메모리 초과가 일어났던 이유
지훈이의 경로탐색이 수행될 때, 해당 좌표의 방문 여부를 확인하지 않아서 방문했던 좌표도 큐에 담아버려 메모리 초과가 일어났다. 이후 지훈이의 경로탐색에 필요한 check:[Bool] 배열을 통해 방문하지 않았던 배열에 대해서만 경로탐색을 수행하도록 수정하였다.
오답 판정에 대한 이유
이후 71%에서 계속 오답이 발생했다. 원인은 또다시 지훈이의 경로탐색 부분에서 발생했는데, 단순히 불이 도달하는 시간보다 지훈이의 시간이 더 낮은 경우에 대해서만 경로탐색을 수행했으나( if visited[x][y] > current_time ), 애초에 해당 좌표에 불이 번지는 장소가 아닌 경우에는 visited[x][y]의 값은 0이다. 따라서 방문이 가능한 부분인데도 해당 부분에 대해서는 경로탐색을 수행하지 않아 올바르지 않은 답을 내놓게 된다. 해당 오류는 zero_woo님의 블로그를 보고 반례를 찾아 해결할 수 있었다. (해당글)
반례
3 4 ###F .J#. ###.
정답은 2가 출력되어야 하나, 고치기 전의 코드로는 "IMPOSSIBLE"이 출력된다. 불이 번지지 않는 위치에 대한 예외처리를 하지 않아서 오답처리를 받았던 것이다.
코드
import Foundation
let rc = readLine()!.split(separator: " ").map{Int($0)!}
let r = rc[0]
let c = rc[1]
var j = [[Int]]()
var f = [[Int]]()
var map = Array(repeating: Array(repeating: "", count: c), count: r)
var visited = Array(repeating: Array(repeating: 0, count: c), count: r)
var ans = Int.max
for i in 0..<r{
let input = readLine()!.map{String($0)}
for k in 0..<c{
map[i][k] = input[k]
if map[i][k] == "J"{
j.append([i,k])
}else if map[i][k] == "F"{
f.append([i,k])
}
}
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
func bfs(j:[[Int]],f:[[Int]]){
var level = 0
var q = f
var dq = [[Int]]()
var v = Array(repeating: Array(repeating: false, count: c), count: r)
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]
v[x][y] = true
visited[x][y] = level
for i in 0..<4{
let nx = dx[i] + x
let ny = dy[i] + y
if nx<0 || nx>=r || ny<0 || ny>=c || map[nx][ny]=="#"{continue}
if visited[nx][ny]==0 && !v[nx][ny]{
v[nx][ny] = true
q.append([nx,ny])
}
}
}
level += 1
}
level = 0
q = j
dq = [[Int]]()
v = Array(repeating: Array(repeating: false, count: c), count: r)
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]
v[x][y] = true
if x==0||x==r-1||y==0||y==c-1{
ans = min(ans, level+1)
}
for i in 0..<4{
let nx = curr[0]+dx[i]
let ny = curr[1]+dy[i]
if nx<0 || nx>=r || ny<0 || ny>=c || map[nx][ny] == "#"{ continue }
if visited[nx][ny] > level+1 && !v[nx][ny]{
v[nx][ny] = true
q.append([nx,ny])
}
if visited[nx][ny]==0 && !v[nx][ny]{
v[nx][ny] = true
q.append([nx,ny])
}
}
}
level += 1
}
}
bfs(j: j, f: f)
print(ans == Int.max ? "IMPOSSIBLE":ans)
비록 해답을 찾아보고 풀게 된 문제이지만, 그래프 탐색에 대한 시야가 아주 조금은 넓어지게 된 문제다.
