3055. 탈출 (Swift, Python)

3055번: 탈출

 

풀이

 물이 차있는 지역과 고슴도치의 위치를 담기 위해 큐를 두 개 만들었다. 각각의 큐에는 좌표(x, y)와 시간(time) 정보가 들어간다. 처음에 입력을 받으면서 time이 0인 값으로 큐를 담아준다.

 

 고슴도치의 위치에서 bfs 탐색을 하면서 시간 정보를 비교해준다. prev_time 변수를 하나 만들어서 이전의 시간을 담아두고 큐에서 값을 꺼낼때마다 둘을 비교해준다. 만약 둘의 값이 다르다면 물을 확장시키는 flood 함수를 호출한다. 

 

 물이 차 있는 지역을 담기 위한 큐에도 시간 정보를 넣어줬는데 물이 무한히 확장시키는걸 방지하기 위해서 넣었다. flood 함수를 호출할 때 현재 몇 초가 흘렀는지를 파라미터로 넘겨준다. 예를 들어 now_time 값으로 2가 들어왔는데 물을 확장시키기 위해 큐에서 값을 꺼내는 과정에서 2가 아닌 시간 값이 나왔다면 다시 큐에 해당 정보를 넣어주고 물을 확장시키는 것을 중지한다.

 

 이렇게 bfs 탐색을 하면서 D의 위치를 만나게 되면 걸린 시간을 반환해주지만 만약 비버 굴에 도달하지 않는다면 -1을 반환해주어 결과값에 따라서 KAKTUS 출력 여부를 결정한다.

 

코드

[Swift]

typealias queueElement = (x: Int, y: Int, time: Int)
 
func isRange(_ x: Int, _ y: Int) -> Bool {
    return 0 <= x && x < R && 0 <= y && y < C
}
 
// now_time : 현재 시간정보 -> 2가 들어오면 2초에서 3초까지만 물의 확장을 하기 위한 파라미터 정보
func flood(_ now_time: Int) {
    while !waters.isEmpty {
        let tmp = waters.removeFirst()
        let x: Int = tmp.x
        let y: Int = tmp.y
        let time: Int = tmp.time
        
        // time이 달라졌다면 now_time에서 확장할 수 있는 위치를 모두 확장시킨 상태이므로 더 이상 확장을 진행하지 않음
        if time != now_time {
            waters.append(tmp)
            return
        }
        
        for i in 0..<4 {
            let nx: Int = x + dx[i]
            let ny: Int = y + dy[i]
            
            if !isRange(nx, ny) || map[nx][ny] == "D" || map[nx][ny] == "X" || map[nx][ny] == "*" {
                continue
            }
            
            map[nx][ny] = "*"
            waters.append((nx, ny, time + 1))
        }
    }
}
 
func bfs() -> Int {
    var prev_time: Int = 0 // 이전 시간
    
    while !q.isEmpty {
        let tmp = q.removeFirst()
        let x: Int = tmp.x
        let y: Int = tmp.y
        let time: Int = tmp.time
        
        // 시간 정보가 이전과 바뀌었으면 물을 확장시킨다.
        if time != prev_time {
            flood(prev_time)
            prev_time = time
        }
        
        // 고슴도치가 [x][y]로 이동했지만 [x][y]로 물이 확장됐으므로 원래 해당 위치는 고슴도치가 가지 못하는 위치였다.
        // 그러므로 continue 해주어 이후 탐색을 못하도록 한다.
        if map[x][y] == "*" {
            continue
        }
        
        for i in 0..<4 {
            let nx: Int = x + dx[i]
            let ny: Int = y + dy[i]
 
            if !isRange(nx, ny) || map[nx][ny] == "X" || map[nx][ny] == "*" || visited[nx][ny] {
                continue
            }
            
            // [nx][ny]가 비버의 굴이면 시간 값을 리턴해준다.
            if map[nx][ny] == "D" {
                return time + 1
            }
            
            visited[nx][ny] = true
            q.append((nx, ny, time+1))
        }
    }
    
    return -1
}
 
var R: Int = 0 // 행
var C: Int = 0 // 열
 
if let input = readLine() {
    let inputs = input.split(separator: " ").map { Int($0)! }
    
    R = inputs[0]
    C = inputs[1]
}
 
var map: [[Character]] = Array(repeating: Array(repeating: "0", count: C), count: R) // 숲
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: C), count: R) // 방문 여부
 
var waters: [queueElement] = [] // 물의 위치 큐
var q: [queueElement] = [] // 고슴도치 위치 큐
 
let dx: [Int] = [1, -1, 0, 0]
let dy: [Int] = [0, 0, 1, -1]
 
for i in 0..<R {
    if let input = readLine() {
        for j in 0..<C {
            let tmp = input[input.index(input.startIndex, offsetBy: j)]
 
            map[i][j] = tmp
 
            if tmp == "S" {
                q.append((i, j, 0))
                visited[i][j] = true
            } else if tmp == "*" {
                waters.append((i, j, 0))
            }
        }
    }
}
 
let res: Int = bfs()
 
if res == -1 {
    print("KAKTUS")
} else {
    print(res)
}
 

 

[Python]

from collections import deque
 
# now_time : 현재 시간정보 -> 2가 들어오면 2초에서 3초까지만 물의 확장을 하기 위한 파라미터 정보
def flood(now_time):
    while waters:
        x, y, time = waters.popleft()
 
        # time이 달라졌다면 now_time에서 확장할 수 있는 위치를 모두 확장시킨 상태이므로 더 이상 확장을 진행하지 않음
        if time != now_time:
            waters.append((x, y, time))
            return
 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if not(0 <= nx < R and 0 <= ny < C) or map[nx][ny] == 'D' or map[nx][ny] == 'X' or map[nx][ny] == '*':
                continue
 
            map[nx][ny] = '*'
            waters.append((nx, ny, time+1))
 
 
def bfs():
    prev_time = 0 # 이전 시간
 
    while q:
        x, y, time = q.popleft()
 
        # 시간 정보가 이전과 바뀌었으면 물을 확장시킨다.
        if time != prev_time:
            flood(prev_time)
            prev_time = time
 
        # 고슴도치가 [x][y]로 이동했지만 [x][y]로 물이 확장됐으므로 원래 해당 위치는 고슴도치가 가지 못하는 위치였다.
        # 그러므로 continue 해주어 이후 탐색을 못하도록 한다.
        if map[x][y] == '*':
            continue
 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if not(0 <= nx < R and 0 <= ny < C) or map[nx][ny] == 'X' or map[nx][ny] == '*' or visited[nx][ny]:
                continue
            
            # [nx][ny]가 비버의 굴이면 시간 값을 리턴해준다.
            if map[nx][ny] == 'D':
                return time+1
 
            visited[nx][ny] = True
            q.append((nx, ny, time+1))
 
    return -1
 
 
if __name__ == '__main__':
    R, C = map(int, input().split()) # 행과 열
    map = [[0] * C for _ in range(R)] # 숲
    visited = [[False] * C for _ in range(R)] # 방문 여부
 
    waters = deque() # 물의 위치 큐
    q = deque() # 고슴도치 위치 큐
 
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
 
    for i in range(R):
        tmp = input()
 
        for j in range(C):
            map[i][j] = tmp[j]
 
            if tmp[j] == 'S':
                q.append((i, j, 0))
                visited[i][j] = True
 
            if tmp[j] == '*':
                waters.append((i, j, 0))
 
    res = bfs()
 
    if res == -1:
        print('KAKTUS')
    else:
        print(res)