[백준/Swift] 5427 : 불

• 백준 5427 : 불

• 문제 소개
• 풀이 과정
• 코드 구현

 

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

5427번: 불

 

문제 소개

 

매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져 나갑니다.

상근이 또한 동서남북 인접한 빈 공간으로 이동할 수 있습니다.

이때 불은 벽에 붙을 수 없고 상근이 또한 벽 통과 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()