Hyun's_Devlog

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

오답 판정으로 고생했던 문제. 다른 분의 풀이를 보니 접근 불가능한 문을 마주했을 때와 이후 열쇠를 얻어 방문할 수 있게 되는 부분에서의 처리방법이 달랐다. 

풀이

bfs를 수행할 때 크게 4가지 조건을 확인하면서 경로를 탐색해야 한다.

• 빈 공간을 마주한 경우
• 문서를 마주한 경우
• 문을 마주한 경우
• 열쇠를 마주한 경우

문서와 빈 공간의 경우 알맞게 처리하고 경로탐색을 수행하면 된다.

헤맸던 부분은 열쇠를 마주했던 부분이다. 문과 열쇠 각각 두 가지 경우로 다시 나뉜다.

• 열 수 있는 문을 마주한 경우 -> 그대로 경로 탐색 수행
• 열 수 없는 문을 마주한 경우 -> 해당 좌표를 담아두고 다음 경로 탐색
• 이미 얻었던 열쇠를 마주한 경우 -> 그대로 경로 탐색 수행
• 기존에 없던 열쇠를 마주한 경우 -> 기존에 마주했던 열 수 없었던 문들 중 해당 열쇠로 열 수 있는 문 좌표에 대해 경로 탐색 수행

기존의 코드는 맵을 입력받을 때 모든 문의 좌표를 담아두고 경로탐색 시 새로운 열쇠를 얻을 때마다 좌표를 담아두었던 배열을 돌며 탐색을 수행했었다. 문제는 그렇게 되면 벽으로 둘러싸여 도달할 수 없는 문의 경우를 매번 마주해야 하고, 이러한 예외처리를 해주어야 하는데, 거기서 부터 해결을 못해 오답 판정을 받았다.

그리고 또 한번 곤욕을 겪은 부분이 경로 탐색 시작 지점에 대한 부분이다. 처음엔 문제에서 주어진 대로 맵의 테두리만 돌면서 탐색 가능한 지점을 직접 찾는 코드를 적었다. 여기서부터 시작 가능한 지점에 대해서 다시 한번 위의 4가지 경우에 맞게 예외처리를 해주어야 했고 이렇게 되면서 코드 양도 많아지고 오답 판정을 받았을 때 찾아봐야 할 지점이 너무 많아서 해결을 못했다.

다른 분의 풀이에서 이 부분도 잘 해결한 모습을 찾을 수 있다. 입력받은 맵 주변에 빈 공간으로 한번 둘러주어 map[0][0]에서 경로를 탐색하게 되면 자연스럽게 4가지 조건에 대한 처리가 이루어지게 된다.

//입력된 지도				
*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*
.	.	.	.	.	.	.	.	.	.	.	.	.	*	*	$	*
*	B	*	A	*	P	*	C	*	*	X	*	Y	*	.	X	.
*	y	*	x	*	a	*	p	*	*	$	*	$	*	*	$	* 
*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*
						
//테두리 추가
.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
.	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	.
.	.	.	.	.	.	.	.	.	.	.	.	.	.	*	*	$	*	.
.	*	B	*	A	*	P	*	C	*	*	X	*	Y	*	.	X	.	.
.	*	y	*	x	*	a	*	p	*	*	$	*	$	*	*	$	*	.
.	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	.
.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.

정답 코드

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

답이 생각나지 않아 점화식을 찾아보고 코드를 적어봤는데, 풀이를 이해하고서도 예외처리를 제대로 하지 못해서 오답 판정을 받았다. 결국 코드까지 찾아보고 난 후에야 풀 수 있었던 문제. 역시나 DP문제는 다양한 시점으로 생각하는 연습이 필요한 것 같다.

풀이

암호화된 문자의 길이가 n일 경우, dp:[Int] 배열은 총 n개의 배열로 dp[i]는 0번째 숫자부터 i번째 숫자까지로 만들수 있는 암호의 갯수가 담긴 배열이다. 입력된 암호문구를 순회하면서 현재 숫자가 0보다 크다면 dp[i-1]번째 경우의 수를 이어가면 되고, 추가로 직전 숫자가 0보다 크다면 현재 숫자와 합쳐 두 자리수의 대체 가능한 알파벳을 만들수 있다면 dp[i-2]번째 경우의 수를 추가로 이어가면된다. 즉 점화식은 아래와 같다.

현재 암호가 0보다 크다면,
dp[i] += dp[i-1]
추가로 직전 암호가 0보다 커서 현재 암호와 이어 붙였을 시 10 이상 26 이하라면,
dp[i] += dp[i-2]

점화식을 알았을 때는 간단하게 풀면 되겠다 싶었는데, 문제는 중간에 나오는 0에 대한 처리 부분이었다. 처음에는 중간에 flag 변수를 만들어 분기 처리를 하였는데, 생각보다 처리해야 할 경우가 많아서 오답처리를 받았다. 다른 유형의 문제들은 많은 문제를 풀면서 패턴에 적응해가는 과정을 통해 성장해가는 게 느껴지는 반면, DP문제는 다양한 시각에서 문제를 바라봐야 한다는 점이 여러모로 어렵게 느껴진다. 풀이는 해당 블로그에서 찾았다. 이해하기 쉽게 풀이에 대한 이미지도 있다.

정답 코드

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

처음으로 4차원 배열을 사용하여 풀어본 문제다. 입력 범위가 작아서 메모리 초과는 면할 수 있었다고 생각한다.

풀이

헛간을 표현하는 배열 map은 각 좌표에 스위치로 불을 켤 수 있는 다른 방의 좌표를 담기 위해 map[n][n] = [[a,b]...] 형태의 4차원 배열로 사용한다. 불이 켜져 있는지 확인하는 turnOn[n][n]:[[Bool]]() 배열과 방문 여부를 담는 visited[n][n] = [[Bool]]() 배열을 사용하여 좌표 탐색을 진행하면 된다.

한 가지 특이점은 예제를 보면 불을 켜게 되는 좌표가 현재 방문한 위치와 인접한 곳에 있지 않는 경우이다.([1][3]에 방문했을 때) 따라서 불을 켜게 될 때 불이 켜지게 되는 좌표의 인접 배열을 탐색하여 인접 배열중 방문했던 곳이 있는지 확인하여 기존에 방문했던 좌표에 인접한 곳이라면 다음 좌표 탐색의 큐에 넣으면 된다. 이후 기존과 동일하게 현재 위치를 기점으로 인접 배열을 확인하여 불이 켜져 있고, 방문한 적 없는 좌표를 큐에 추가로 담아 경로탐색을 수행하면 된다.

정답 코드

import Foundation

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var map = Array(repeating: Array(repeating: [[Int]](), count: n), count: n)
var turnOn = Array(repeating: Array(repeating: false, count: n), count: n)
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var ans = 0

for _ in 0..<m{
    let input = readLine()!.split(separator: " ").map{Int(String($0))! - 1}
    let x = input[0]
    let y = input[1]
    let a = input[2]
    let b = input[3]
    map[x][y].append([a,b])
}

let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
func bfs(){
    var q = [[0,0]]
    var dq = [[Int]]()
    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]
            for button in map[x][y]{
                let ax = button[0]
                let by = button[1]
                if !turnOn[ax][by] {
                    turnOn[ax][by] = true
                    ans += 1
                    for i in 0..<4{
                        let nx = ax+dx[i]
                        let ny = by+dy[i]
                        if nx<0 || nx>=n || ny<0 || ny>=n{ continue }
                        if visited[nx][ny]{
                            visited[ax][by] = true
                            q.append([ax,by])
                        }
                    }
                }
            }
            for i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=n || ny<0 || ny>=n{ continue }
                if turnOn[nx][ny] && !visited[nx][ny]{
                    visited[nx][ny] = true
                    q.append([nx,ny])
                }
            }
        }
    }
}

turnOn[0][0] = true
visited[0][0] = true
ans = 1
bfs()
print(ans)

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

bfs를 두 번 사용해서 풀었다. 중간에 변수명이 겹친걸 못 알아채서 쓸데없는 부분에서 시간을 오래 끌었던 문제였다. 조금 더 집중해서 풀이를 생각하는 연습이 필요한 것 같다.

풀이

입력으로 육지와 바다에 대한 구분이 들어온다. 우선 기본적인 bfs를 통해 각 컴포넌트를 구분 짓는 작업을 해준다. 그 이후 한번 더 bfs를 통해 짧은 다리를 찾으면 되는데, 경로탐색의 조건은 다음과 같이 정의했다.

• 상하좌우를 확인하여, 바다인 경우만 큐에 넣고 탐색
• 바다가 아닌 곳이라면 경로탐색 시작 컴포넌트와 다른 컴포넌트인지 확인하여 다른 곳이라면 다리 길이를 갱신 후 종료
• 경로 탐색 중 현재 갱신된 다리 길이보다 길다면 종료

정답 코드

주석 처리된 부분은 알맞게 풀고 있는지 확인하려 적은 코드이다.

import Foundation

let n = Int(readLine()!)!
var map = Array(repeating: [Int](), count: n)
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var land = Array(repeating: Array(repeating: 0, count: n), count: n)

for i in 0..<n{
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    map[i] = input
}

let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
func numbering(x:Int, y:Int, landNumber:Int){
    var q = [[x,y]]
    var dq = [[Int]]()
    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]
            for i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=n || ny<0 || ny>=n || map[nx][ny]==0{ continue }
                if !visited[nx][ny]{
                    visited[nx][ny] = true
                    land[nx][ny] = landNumber
                    q.append([nx,ny])
                }
            }
        }
    }
}

var number = 1
for i in 0..<n{
    for k in 0..<n{
        if !visited[i][k] && map[i][k] != 0{
            visited[i][k] = true
            land[i][k] = number
            numbering(x: i, y: k, landNumber: number)
            number += 1
        }
    }
}
//for l in land{ print(l) }
var ans = n*n
var check = visited
func bridge(ix:Int,ky:Int){
    visited = Array(repeating: Array(repeating: false, count: n), count: n)
    var q = [[ix,ky,0]]
    var dq = [[Int]]()
    let landNumber = land[ix][ky]
    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 cnt = curr[2]
            if cnt > ans{
                return
            }
            for i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=n || ny<0 || ny>=n { continue }
                if !visited[nx][ny] && land[nx][ny]==0{
                    visited[nx][ny] = true
                    q.append([nx,ny,cnt+1])
                }
                if !visited[nx][ny] && land[nx][ny]>0 && land[nx][ny] != landNumber{
//                    print("land[\(ix)][\(ky)]:\(landNumber) -> land[\(nx)][\(ny)]:\(land[nx][ny]), cnt:\(cnt)")
                    ans = min(ans, cnt)
                    return
                }
            }
        }
    }
}

visited = Array(repeating: Array(repeating: false, count: n), count: n)
for x in 0..<n{
    for y in 0..<n{
        if land[x][y]>0{
            bridge(ix: x, ky: y)
        }
    }
}
print(ans)

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

숨바꼭질 시리즈의 문제다. 선행 문제와 같은 방식으로 풀어보려 했으나 이번에는 동생이 움직인다는 조건이 붙어서 오답을 받았다. 풀이를 찾아보고 풀 수 있었던 문제였다. 

풀이

기존의 숨바꼭질 문제에서는 visited[n] 방문 배열을 "거리 n에 도달하는 데에 걸리는 시간"으로 설정하여 경로탐색으로 더 짧은 시간으로 갱신시켜 답을 구했다면 이번에는 동생이 이동한다는 조건 때문에 다른 방식으로 접근해야 한다. 수빈이가 동생이 도착할 장소에 미리 도착하여 한 칸 전진, 한 칸 후진 즉 2초를 소비하여 해당 자리에서 대기하는 것이 가능하다.

그렇다면 구분해야할것은 해당 시간과 위치에 홀수 초에 도착하는지 짝수 초에 도착하는지를 확인하여 해당 시간을 반환하면 된다. 따라서 방문 배열은 visited[t][k]:[[Bool]] 2차원 배열로 설정하고 t%2초에 k번째 위치에 방문했는지를 갱신하여 경로탐색을 해주면 된다. 시간이 갱신될 때마다 동생의 위치 k번째 배열 값이 참이라면 해당 시간을 반환하면 된다. 역시 설명보단 코드가 이해하기 더 쉬울 것이다.

정답 코드

import Foundation

let nk = readLine()!.split(separator: " ").map{Int($0)!}
let n = nk[0]
var k = nk[1]
var ans = -1

var map = Array(repeating: Array(repeating: false, count: 2), count: 500001)
map[n][0] = true
var time = 0

func bfs(){
    var q = [n]
    var dq = [Int]()
    while !q.isEmpty{
        k += time
        dq = q.reversed()
        q.removeAll()
        if k<0 || k>500000{return}
        if map[k][time%2]{
            ans = time
            return
        }
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let next = [curr-1,curr+1,curr*2]
            
            for next in next{
                if next<0 || next>=500001{continue}
                if !map[next][(time+1)%2]{
                    map[next][(time+1)%2] = true
                    q.append(next)
                }
            }
        }
        time += 1
    }
}
bfs()
print(ans)

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

골드 난이도의 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)

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

[4179] 불! 문제보다는 체감상 쉽게 다가왔다. 불! 문제에서 너무 고생해서 그랬나 보다. 물론 한 번에 통과하진 못했고, 결국 답을 찾아보았지만 조금만 더 깊이 생각했으면 답에 도달하지 않았을까 싶다.

풀이

늘 bfs문제를 풀듯이, 상하좌우 좌표의 확인과 말의 이동방식의 좌표 확인 과정을 추가해서 경로를 탐색하면 된다. 중요한 점은 말의 움직임은 k번까지만 가능하고, 말의 움직임과 원숭이의 움직임에 대해 순서가 뒤섞여서 움직일 수 있다는 점이다. 해당 부분에 대한 처리가 어설퍼서 처음에는 오답 판정을 받았다. 

큐에는 다음 좌표와 말의 움직임을 몇번 사용하였는지, 그리고 지금까지의 총 이동 횟수를 담아 확인했다. 이후 방문 여부를 확인하는 visited 배열을 3차원으로 생성하는 것이 핵심이다. visited[k][x][y] 배열을 통해 k번째 말의 움직임과 일반적인 움직임의 조합으로 경로를 탐색한다. 각 k번째 visited 배열에는 해당 횟수에서 이동 가능한 말의 움직임 + 원숭이의 움직임에 대한 방문 여부를 확인하고 경로탐색을 수행하면 된다. 설명보단 코드로 보는 것이 이해하기 더 쉬울 것이다.

오답 코드

해당 코드에서는 말의 움직임에 대해 깊이 고민하지 않고, 일반적인 visited배열을 사용하여 오답 판정을 받았다.

import Foundation

let k = Int(readLine()!)!
let wh = readLine()!.split(separator: " ").map{Int($0)!}
let w = wh[0]
let h = wh[1]
var ans = -1
var length = 0

var map = Array(repeating: Array(repeating: 0, count: w), count: h)
var visited = Array(repeating: Array(repeating: false, count: w), count: h)
for x in 0..<h{
    let land = readLine()!.split(separator: " ").map{Int($0)!}
    for y in 0..<w{
        map[x][y] = land[y]
    }
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
let hx = [-1,-2,-2,-1,1,2,2,1]
let hy = [-2,-1,1,2,2,1,-1,-2]

func bfs(){
    var q = [[0,0,k,length]]
    var dq = [[Int]]()
    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 cnt = curr[2]
            let len = curr[3]
            if x==h-1 && y==w-1{
                ans = len
                return
            }
            
            if cnt>0{
                for i in 0..<8{
                    let nx = x+hx[i]
                    let ny = y+hy[i]
                    if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
                    if !visited[nx][ny]{
                        visited[nx][ny] = true
                        q.append([nx,ny,cnt-1,len+1])
                    }
                }
            }
            for i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
                if !visited[nx][ny]{
                    visited[nx][ny] = true
                    q.append([nx,ny,cnt,len+1])
                }
            }
        }
    }
}
visited[0][0] = true
bfs()
print(ans)

정답 코드

import Foundation

let k = Int(readLine()!)!
let wh = readLine()!.split(separator: " ").map{Int($0)!}
let w = wh[0]
let h = wh[1]
var ans = -1

var map = Array(repeating: Array(repeating: 0, count: w), count: h)
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 31), count: w), count: h)
for x in 0..<h{
    let land = readLine()!.split(separator: " ").map{Int($0)!}
    for y in 0..<w{
        map[x][y] = land[y]
    }
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
let hx = [-1,-2,-2,-1,1,2,2,1]
let hy = [-2,-1,1,2,2,1,-1,-2]

func bfs(){
    var q = [[0,0,0,0]]
    var dq = [[Int]]()
    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 cnt = curr[2]
            let length = curr[3]
            if x==h-1 && y==w-1{
                ans = length
                return
            }
            
            if cnt<k{
                for i in 0..<8{
                    let nx = x+hx[i]
                    let ny = y+hy[i]
                    if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
                    if !visited[nx][ny][cnt+1]{
                        visited[nx][ny][cnt+1] = true
                        q.append([nx,ny,cnt+1,length+1])
                    }
                }
            }
            for i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
                if !visited[nx][ny][cnt]{
                    visited[nx][ny][cnt] = true
                    q.append([nx,ny,cnt,length+1])
                }
            }
        }
    }
}
visited[0][0][0] = true
bfs()
print(ans)

https://www.acmicpc.net/problem/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)

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