[4179] 불!

https://www.acmicpc.net/problem/4179

4179번: 불!

정답에 닿을 듯 말듯해서 더욱 고생했던 문제다. 메모리 초과를 마주해서 고생하고, 이후 오답으로 인해 한번 더 고생했다.

 

풀이

문제를 보면 알겠지만 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)

비록 해답을 찾아보고 풀게 된 문제이지만, 그래프 탐색에 대한 시야가 아주 조금은 넓어지게 된 문제다.