문제 링크 : https://www.acmicpc.net/problem/3197
BFS 문제. 처음 풀어본 플레티넘 등급 문제였다.
얼음을 녹이는 문제여서 그런지 그전에 풀어봤던 2573번 빙산과 비슷한 문제처럼 느껴졌다. 빙산 문제에선 얼음이 녹을 때마다 얼음이 다 녹거나 얼음이 두 덩이 이상으로 분리되는 걸 체크해서 풀었는데, 이번 문제는 얼음이 녹을 때마다 백조끼리 만날 수 있는지 BFS를 돌리면 되지 않을까? 라는 생각으로 접근하였다.
처음엔 단순하게 하루가 지날 때마다 모든 물을 확인해서 얼음을 녹이고, 백조의 위치에서 다른 백조의 위치까지 도달하는지 확인하였더니 시간초과가 났다.
얼음을 녹이기 위해 모든 물을 확인하는 데에는 O(RC)가 걸리고, 또 백조들이 만날 수 있는지 확인하는 데에도 최악의 경우 O(RC)와 가까운 코드를 탄생시켜버렸다. 문제에서의 R과 C는 1500까지 주어지므로 1500x1500은 200만이 넘으니 시간초과는 당연한 결과였다.
풀이과정
입력 및 초기화
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (R, C) = (input[0], input[1])
var visit = Array(repeating: Array(repeating: false, count: C), count: R)
let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]
var map = [[String]]()
var (sx, sy) = (-1, -1) // 0번째 백조 x, y 좌표
var (ex, ey) = (-1, -1) // 1번째 백조 x, y 좌표
var swanQueue: [(Int, Int)] = [] // 백조가 방문할 좌표 queue
var waterQueue: [(Int, Int)] = [] // 녹게될 빙판 좌표 queue
물, 빙판, 백조가 있는 공간을 입력할 때 주의해야 할 점이 있다.
문제를 분명 제대로 다 푼 거 같았는데 검토를 열심히 하고 몇 번이고 제출해도 결과는 틀렸다고만 나와서 내가 모르는 예외가 있지 않을까 해서 검색해보다가 반례를 찾게 되었다. 그때 당시에는 생각하지 못한 반례가 있었는데, 바로 백조가 있는 곳도 물이라는 점이다.
LXX.XXL이 입력으로 들어왔을 때, 하루 뒤의 상황은 LX..XL이 아니라 백조가 있는 곳도 물이기 때문에 L....L가 되는것이다.
이 예외를 처리해주기 위해 입력을 받을 때, 백조가 있는곳도 물로 만들어 주었다.
// 물, 빙판, 백조 입력
for i in 0..<R {
map.append(readLine()!.map{ String($0) })
for j in 0..<C {
if map[i][j] == "L" {
if sx == -1 && sy == -1 {
sx = i; sy = j // 0번째 백조 좌표 저장
} else {
ex = i; ey = j // 1번째 백조 좌표 저장
}
map[i][j] = "." // 백조가 있는 곳을 물으로 만듬
// 1 7
// LXX.XXL 으로 입력되었을 때의 상황 예외처리
waterQueue.append((i, j))
} else if map[i][j] == "." {
waterQueue.append((i, j))
}
}
}이제 시간초과 문제를 해결해야 한다. 시간을 단축하기 위해서는 오늘 방문했던 위치를 그다음 날엔 방문하지 않게 처리해주면 된다. 다르게 말하자면 다음날 방문할 좌표들을 새로운 Queue에 저장하고 현재 Queue에 대입해줌으로 그다음 날엔 어제 방문했던 위치를 방문하지 않게 된다.
1. 빙판의 경우 BFS를 돌면서 다음날 방문할 빙판을 찾아 그 좌표를 새로 생성한 Queue에 저장하고 BFS가 종료됐을 때 기존의 waterQueue에 새로 생성한 nextWaterQueue를 대입한다.
func meltIce() {
var nextWaterQueue: [(Int, Int)] = [] // 그 다음날 방문할 빙판
var front = 0
while front < waterQueue.count {
let (x, y) = waterQueue[front]
front += 1
for i in 0...3 {
let nX = x + dx[i]
let nY = y + dy[i]
if nX < 0 || nY < 0 || nX >= R || nY >= C {
continue
}
if map[nX][nY] == "X" { // 빙판을 찾을 경우
// 물로 만들어주고 queue에 좌표를 추가
map[nX][nY] = "."
nextWaterQueue.append((nX, nY))
}
}
}
// 기존의 Queue에 새로 생성한 Queue 대입
waterQueue = nextWaterQueue
}
2. 백조의 경우 BFS를 돌면서 물에서 가장 인접한 빙판(오늘은 빙판이지만 그다음 날은 녹아서 물이 된다)을 찾는다. 새로 생성한 Queue에 저장하고 BFS가 종료됐을 때 기존의 swanQueue에 새로 생성한 Queue를 대입한다.
func moveSwan() -> Bool {
var nextSwanQueue: [(Int, Int)] = [] // 다음날 녹아서 물이 될 빙판(다음날 백조가 갈 곳)
var front = 0
while front < swanQueue.count {
let (x, y) = swanQueue[front]
front += 1
if x == ex && y == ey { // 다른 백조와 만났다면 return true
return true
}
for i in 0...3 {
let nX = x + dx[i]
let nY = y + dy[i]
if nX < 0 || nY < 0 || nX >= R || nY >= C || visit[nX][nY] {
continue
}
visit[nX][nY] = true
if map[nX][nY] == "X" {
nextSwanQueue.append((nX, nY))
continue
}
swanQueue.append((nX, nY))
}
}
swanQueue = nextSwanQueue
return false // 다른 백조와 만나지못했으므로 return false
}
전체코드
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (R, C) = (input[0], input[1])
var visit = Array(repeating: Array(repeating: false, count: C), count: R)
let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]
var map = [[String]]()
var (sx, sy) = (-1, -1) // 0번째 백조 x, y 좌표
var (ex, ey) = (-1, -1) // 1번째 백조 x, y 좌표
var swanQueue: [(Int, Int)] = [] // 백조가 방문할 좌표 queue
var waterQueue: [(Int, Int)] = [] // 녹게될 빙판 좌표 queue
for i in 0..<R {
map.append(readLine()!.map{ String($0) })
for j in 0..<C {
if map[i][j] == "L" {
if sx == -1 && sy == -1 {
sx = i; sy = j
} else {
ex = i; ey = j
}
map[i][j] = "."
// 1 7
// LXX.XXL 상황 예외처리
waterQueue.append((i, j))
} else if map[i][j] == "." {
waterQueue.append((i, j))
}
}
}
func meltIce() {
var nextWaterQueue: [(Int, Int)] = [] // 그 다음날 방문할 빙판
var front = 0
while front < waterQueue.count {
let (x, y) = waterQueue[front]
front += 1
for i in 0...3 {
let nX = x + dx[i]
let nY = y + dy[i]
if nX < 0 || nY < 0 || nX >= R || nY >= C {
continue
}
if map[nX][nY] == "X" { // 빙판을 찾을 경우
// 물로 만들어주고 queue에 좌표를 추가
map[nX][nY] = "."
nextWaterQueue.append((nX, nY))
}
}
}
// 기존의 Queue에 새로 생성한 Queue 대입
waterQueue = nextWaterQueue
}
func moveSwan() -> Bool {
var nextSwanQueue: [(Int, Int)] = [] // 다음날 녹아서 물이 될 빙판(다음날 백조가 갈 곳)
var front = 0
while front < swanQueue.count {
let (x, y) = swanQueue[front]
front += 1
if x == ex && y == ey { // 다른 백조와 만났다면 return true
return true
}
for i in 0...3 {
let nX = x + dx[i]
let nY = y + dy[i]
if nX < 0 || nY < 0 || nX >= R || nY >= C || visit[nX][nY] {
continue
}
visit[nX][nY] = true
if map[nX][nY] == "X" {
nextSwanQueue.append((nX, nY))
continue
}
swanQueue.append((nX, nY))
}
}
swanQueue = nextSwanQueue
return false // 다른 백조와 만나지못했으므로 return false
}
swanQueue = [(sx, sy)] // 0번째 백조
visit[sx][sy] = true // 방문 체크
var answer = 0
while true {
if moveSwan() { break } // 백조가 서로 만날 수 있는지 확인
// 서로 만날수 없다면
meltIce() // 물과 접촉한 빙판 녹이기
answer += 1 // 하루가 지남
}
print(answer)
결과
시간초과 문제를 해결하기 위해 메서드가 실행될 때마다 기존 큐의 데이터를 변경함으로써 이전에 방문했던 곳을 가지 않게 처리해줄 수 있다는 점이 지금까지 풀어봤던 BFS 문제 중에서 가장 인상 깊었고 많은 깨달음을 얻은 문제였다.
매일 발전하는 초보 개발자입니다.
댓글은 언제나 환영합니다.
잘못되었거나 더 효율적인 코드가 있다면 댓글 부탁드립니다!
IOS Developer
저는 큰돌 강의 보면서 swift로 이 문제 풀고있는데, bfs를 구현할 때 직접 삭제 동작이 들어가게 되니깐
시간 초과가 나더라고요 ( removeFirst 말고 Queue를 직접 구현해서 popLast로 삭제하게 했는데)
그런데 은표님의 front와 while을 사용한 풀이 덕분에 직접 팝을 안 하게 되니 시간초과를 넘겼습니다.
감사합니다 !!