[백준/Swift] 3055 : 탈출

 

• 백준 BFS 탈출 문제

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

 

 

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

3055번: 탈출

 

문제 소개

 

매 분마다 물이 고인 곳에서 주변 으로 한칸씩 범람하는데, 고슴도치 또한 돌, 물이 없는 곳을 통해 한 칸 씩 이동할 수 있습니다.

최종적으로 고슴도치가 비버의 굴로 이동하면 걸린 시간을 출력 else "KAKTUS"를 출력하는 bfs 문제입니다.

 

  문제에서 주어진 키워드

• R행 C열
• 비어있는 지역     =  .
• 물이 차있는 지역 = *
• 돌이 있는 지역    = X
• 고슴도치 위치     = S
• 물, 도치 이동     = 상, 하, 좌, 우
• D와 S는 하나씩 
• 매 분마다 물도 범람하고 고슴도치도 한 칸 이동 가능

 

풀이 과정

 

물과 고슴도치가 이동하는 위치를 알 수 있게,

BFS탐색을 하기위해 우선 큐를 선언습니다.

typealias qElement = (p : point, time: Int)

//고슴도치 이동 좌표와 물이 차는 위치 좌표 담을 큐
class queue
{
    var q : [qElement]
    var index : Int
    init()
    {
        q = [qElement]()
        index = 0
    }
}

그 후 

var dochiQ    = queue()
var waterQ    = queue()

고슴도치가 이동하는 위치를 저장하기 위한 큐,

물이 범람하는 위치를 저장하기 위한 큐를 선언했다.

이때 queue의 list에는 좌표와 특정 위치에서의 시간을 저장했습니다.

 

func escape() 에서는 고슴도치가 이동을 합니다.

 

• 이때 중요한 점이 있습니다. 반드시 매 분마다 bfs가 한번 실행 되어야 한다는 점입니다.

이를 해결하기 위해서 저는 큐에 서 특정 위치를 꺼낼 때 해당 좌표에 도착한 시간과 현재시간이 같지 않다면 계속해서 큐의 list의 좌표들을 bfs탐색을 해나가고 이후에 list에서 꺼낸 특정 point의 시간이 현재시간과 같을때 그때 비로소 현재시간을 증가함으로 위 문제를 해결했습니다.

• 또 중요한 점은 중간에 비버가 이동할 자리가 모두 물로 찼다면 무한 루프에 빠질 가능성이 있어 주의 해야 합니다.

만약에 큐의 list탐색을 끝낼 때 까지 "D"에 도착하지 않으면 물에 잠긴것으로 판단되어서 KAKTUS 판정을 결론짓는 것입니다.

 

 

코드 구현

 

import Foundation

typealias qElement = (p : point, time: Int)
// 좌표
class point
{
    var x : Int
    var y : Int
    init(_ x : Int, _ y : Int)
    {
        self.x = x
        self.y = y
    }
}
//고슴도치 이동 좌표와 물이 차는 위치 좌표 담을 큐
class queue
{
    var q : [qElement]
    var index : Int
    init()
    {
        q = [qElement]()
        index = 0
    }
}
/**
 * forest 크기
 */
class rect
{
    var width  : Int
    var height : Int
    init()
    {
        if let hw = readLine()
        {
            let input = hw.split(separator: " ").map{Int($0)!}
            height = input[0]
            width  = input[1]
        }else
        {
            width  = -1
            height = -1
        }
    }
}

//범위 벗어났는가?
func isOutForest(p : point, rect: rect) -> Bool
{
    if p.x < 0 || p.x > rect.width - 1 || p.y < 0 || p.y > rect.height - 1
    {
        return true
    }
    return false
}
/**
 * 고슴도치의 목숨이 담긴 함수
 * 이 함수에서 while문이 끝나기 전까지 return 을 안하면 고슴도치의 운명은.... ㅠㅠ
 */
func escape(rect : rect, time : inout Int,fallIn : inout Bool, dochiQ : inout queue, waterQ : inout queue, forest : [[String]], direction : [(Int,Int)], visited : inout [[Bool]])
{
    
    while dochiQ.q.count != dochiQ.index
    {
        let (curPoint,prevTime) = dochiQ.q[dochiQ.index]
        if prevTime == time { time += 1 }
        dochiQ.index += 1
        
        flood(rect: rect, time: time, fallIn: &fallIn, queue: &waterQ, forest: forest, direction: direction, visited: &visited)

        
        for (dx,dy) in direction
        {
            let (nx,ny) = (curPoint.x + dx, curPoint.y + dy)
            if isOutForest(p: point(nx, ny), rect: rect) { continue }
            
            if forest[ny][nx] == "D"
            {
                return
            }
            
            if forest[ny][nx] == "." && !visited[ny][nx]
            {
                visited[ny][nx] = true
                dochiQ.q.append((point(nx, ny),prevTime + 1))
            }
        }
    }
    fallIn = true
}
// 숲에 매 분마다 물이 (주위로)범람함
func flood(rect : rect, time : Int, fallIn : inout Bool, queue : inout queue, forest : [[String]], direction : [(Int,Int)], visited : inout [[Bool]])
{
    while queue.q.count != queue.index
    {
        let (curPoint,prevTime) = queue.q[queue.index]
        if prevTime == time { return }
        queue.index += 1
        
        for (dx,dy) in direction
        {
            let (nx,ny) = (curPoint.x + dx, curPoint.y + dy)
            if isOutForest(p: point(nx, ny), rect: rect) || forest[ny][nx] == "D" || forest[ny][nx] == "X" { continue }
            
            if forest[ny][nx] == "." && !visited[ny][nx]
            {
                visited[ny][nx] = true
                queue.q.append((point(nx, ny),prevTime + 1))
            }
        }
    }
}

/**
 * @param direction : 특정 좌표가 이동할 수 있는 범위
 * @param rect         : 숲(맵) 크기 info
 * @param forest      : 숲(맵)
 * @param visited     : 방문했는가?
 * @param dochiQ    : 도치가 이동할 곳
 * @param waterQ    : 물이 범람하는 곳
 * @param fallIn        : 도치가 물에 빠졌는가?
 * @param time        : 분 체크
 */
func BOJ_3055()
{
    let direction = [(-1,0),(1,0),(0,1),(0,-1)]
    
    let rect      = rect()
    var forest    = Array(repeating: [String](), count: rect.height)
    var visited   = Array(repeating: Array(repeating: false, count: rect.width), count: rect.height)
    var dochiQ    = queue()
    var waterQ    = queue()
    var fallIn    = false
    var time      = 0
    
    // 도치 위치와 물 위치 받음
    for y in 0..<rect.height
    {
        if let col = readLine()
        {
            forest[y] = col.map{String($0)}
        }
        for x in 0..<rect.width
        {
            if forest[y][x] == "S"
            {
                dochiQ.q.append((point(x, y), 0))
                visited[y][x] = true
            } else if forest[y][x] == "*"
            {
                waterQ.q.append((point(x,y),0))
            }
        }
    }
    
    //도치의 여정
    escape(rect: rect, time: &time, fallIn: &fallIn, dochiQ: &dochiQ, waterQ: &waterQ, forest: forest, direction: direction, visited: &visited)
    
    print(fallIn == true ? "KAKTUS" : "\(time)")
}
BOJ_3055()