https://www.acmicpc.net/problem/5427
5427번: 불
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에
www.acmicpc.net
문제 소개
매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져 나갑니다.
상근이 또한 동서남북 인접한 빈 공간으로 이동할 수 있습니다.
이때 불은 벽에 붙을 수 없고 상근이 또한 벽 통과 x 불 붙으려는 칸 이동할 수 없습니다.
하지만 상근이가 있는 자리에서 1초가 지나 불이 상근이쪽으로 올 때 (동시에)상근이는 다른 칸으로 이동할 수 있습니다.
이 문제는 매 초마다 불이 번지기 이전에 맵 밖을 나가면 탈출을 하는 문제입니다.
문제에서 알려준 핵심 키워드는
매 초 마다 불과 상근이는 한 칸씩 이동할 수 있다는 것입니다.
이때 BFS를 사용할 수 있습니다. 하지만 주의해야 할 점이 특정한 시간대에 불이 한칸씩 번져야 합니다.
저는 이를 해결하기 위해 큐에서 탐색하기 위한 x,y축을 저장함과 동시에 현재 시간대를 저장해주었습니다.
/**
* @param qElement : (현재x축, 현재y축, 시간)
*/
typealias qElement = (Int,Int,Int)
class Queue
{
var queue : [qElement]
var index : Int
init()
{
queue = [qElement]()
index = 0
}
}
예를 들자면
상근이 이동할 곳 저장하는 큐 queue
불이 이동할 것 저장하는 큐 fireQ
초기에 발견된 상근이는 queue에 (x,y,0)으로
불은 fireQ에 (x,y,0)으로 저장합니다.
이후 currentTime 현재시간을 1로 두었을 때 비로소 불과 상근이는 이동합니다.
상근이를 기준으로 초기에 저장된 위치와 시간0 에 대해서 현재 시간과 같지 않을 때까지 빈 공간을 탐색합니다. 이때 발견된 빈 공간은 prevTime + 1을 새로운 시간과 자표로 queue에 저장합니다.
이런 식입니다. prevTime이 currentTime과 같을 경우에 비로소 불도 근접한 한칸씩 이동, 상근이도 한칸씩 이동을 할 수 있습니다.
bfs탐색을 전제 하에 입니다.
언제까지? 상근이의 queue에 탐색할 공간이 더이상 없을 때까지.
상근이의 탈출은 상 하 좌우로 이동한 지역이 맵을 벗어났을 때 상 하 좌 우로 이동하기 전의 상태가 "@"인 경우 상근이가 탈출한 케이스이므로 그때 탈출에 성공했음으로 코드를 구현했습니다.
풀이 과정
맨 처음에는 한개의 큐에 상근이 먼저 큐에 저장 후 불 위치를 저장하는 방식으로 한개의 queue에 저장 후 removeFirst()함수를 써서 사용했는데 시간초과가 걸렸습니다.
이후 상근이 위치 따로 불 위치 따로 위에처럼 두개의 큐를 사용해 각각 저장 한 후
removeFirst()함수를 써가며 풀었는데 시간초과가 났습니다.
그래서 removeFirst()함수를 사용하지 않고 이번엔 두개의 큐에 각각 대응되는 index를 포함한 클래스를 만들어서 각각 index를 탐색하는 방식으로 구현했는데 그 결과 정답이 되었습니다.
...
removeFirst()별로 안좋다는 것을 다시 한번 깨닫았습니다...이거때매 한~두 시간을 해맸네요 ㅠㅠ;;
코드 구현
import Foundation
/**
* @param qElement : (x좌표,y좌표, x-y좌표 탐색시 현재 시간)
*/
typealias qElement = (Int,Int,Int)
/**
* removeFirst()를써서 시간초과 났습니다.
* 큐에 원소들 삭제 안하고 index로 훑는 방식을 쓰려고 큐 클래스를 만들었습니다.
*/
class Queue
{
var queue : [qElement]
var index : Int
init()
{
queue = [qElement]()
index = 0
}
}
/**
* 불에 의해 prevTime != (current)Time일때까지
* 큐에 존재하는 원소들을 통해 빈 지점을 계속해서 탐색해 나갑니다.
* 만약 prevTime = Time일 경우 1초가 지난 것으로 판단하고 break합니다.
*/
func fire(_ width : Int, _ height : Int, _ time : Int, _ building : inout [[String]], _ queue : inout Queue)
{
let direction = [(-1,0),(1,0),(0,1),(0,-1)]
while queue.queue.count != queue.index
{
//prevTime == currentTime인가? (1초지난거로 판단)
if queue.queue[queue.index].2 == time
{break}
let (curX,curY,prevTime) = queue.queue[queue.index]
queue.index += 1
for (dx,dy) in direction
{
let (nx, ny) = (dx + curX, dy + curY)
if nx < 0 || nx > width - 1 || ny < 0 || ny > height - 1
{
continue
}
//빈 지점 불태워~
if building[ny][nx] == "."
{
queue.queue.append((nx,ny,prevTime + 1))
building[ny][nx] = "*"
}
//상근이가 있을 수 있는 케이스인데 이 또한 안되므로 불로 바꾸었습니다.
if building[ny][nx] == "@"
{
building[ny][nx] = "*"
}
}
}
}
/**
* 상근이의 탈출 입니다.
* time은 현재시간이고, 앞으로 이 시간이 증가되는데 증가될 때마다
* fire에 의해 먼저 빈 지역이 불타고
* 이와 동시에 상근이도 탈출 가능성 있는 지역을 bfs로 queue에 집어넣으면서
* 매 초마다 상근이가 탈출 할 지점을 찾아서 탈출을 하게 된다면
*
*
* 맵 지역을 벗어나는 것인데 이때 단순하게 맵 지역 벗어나는 체크를 할 때 curX,Y가 "@"이면 탈출 성공으로 간주하고 isEscape 를 true로 바꿨습니다.
* 만약 escape가 종료되었음에도 isEscape 변수가 false면 상근이는 탈출하지 못한 것이므로 임파써블을 출력하도록 했습니다.
*/
func escape(_ width : Int, _ height : Int, _ res : inout String, _ isEscape : inout Bool, _ building : inout [[String]], _ queue : inout Queue, _ fQueue : inout Queue)
{
var time = 0
let direction = [(-1,0),(1,0),(0,1),(0,-1)]
while queue.queue.count != queue.index
{
let (curX,curY,prevTime) = queue.queue[queue.index]
queue.index += 1
if prevTime == time
{
fire(width, height, time, &building, &fQueue)
time += 1
}
for (dx, dy) in direction
{
let (nx,ny) = (curX + dx, curY + dy)
if nx < 0 || nx > width - 1 || ny < 0 || ny > height - 1
{
if building[curY][curX] == "@"
{
isEscape = true
res += "\(time)\n"
return
}
continue
}
if building[ny][nx] == "." && building[curY][curX] == "@"
{
building[ny][nx] = "@"
queue.queue.append((nx,ny,prevTime + 1))
}
}
}
}
func BOJ_5427()
{
let n = Int(readLine()!)!
var res = ""
for _ in 0..<n
{
var isEscape = false
let wh = readLine()!.split(separator: " ").map{Int(String($0))!}
let width = wh[0]
let height = wh[1]
var building = Array(repeating: [String](), count: height)
var queue = Queue()
var fireQ = Queue()
for y in 0..<height
{
building[y] = readLine()!.map{String($0)}
for x in 0..<width
{
if building[y][x] == "@"
{
queue.queue.append((x,y,0))
}
if building[y][x] == "*"
{
fireQ.queue.append((x,y,0))
}
}
}
escape(width, height, &res, &isEscape, &building, &queue, &fireQ)
if !isEscape
{
res += "IMPOSSIBLE\n"
}
}
print(res)
}
BOJ_5427()
'백준 PS일지 > DFS&BFS' 카테고리의 다른 글
[백준/Swift] 16234 : 인구이동 (0) | 2022.07.02 |
---|---|
[백준/Swift] 2146 : 다리 만들기 (0) | 2022.06.29 |
[백준/Swift] 1697 : 숨바꼭질 (0) | 2022.06.24 |
[백준/Swift] 3055 : 탈출 (0) | 2022.06.24 |