[BOJ] Q3055 탈출

[BOJ] Q3055 탈출

Question

Language: Python

Difficulty: Gold 4

해당 문제는 4179와 유사한 방식으로 문제를 풀이하면 된다.

bfs 1: 물의 이동

#물의 이동 수행
visited=[[False] * n_cols for _ in range(n_rows)]
while water_queue:
    row,col,time=water_queue.popleft()
    
    #이전에 방문한 경우
    if visited[row][col]:
        continue
    visited[row][col]=True
    #물이 해당 좌표에 도달하는 시간
    time_map[row][col]=time
    

    for dir in range(4):
        next_row=row+dy[dir]
        next_col=col+dx[dir]
        #범위를 넘어서는 경우
        if next_row < 0 or next_row>=n_rows or next_col<0 or next_col>=n_cols:
            continue
        #다음 좌표가 돌인 경우
        if board[next_row][next_col]=="X":
            continue
        #물은 목적지 좌표에 도달할 수 없다.
        if board[next_row][next_col]=="D":
            continue

        water_queue.append((next_row,next_col,time+1))

매분 마다 동시에 이동하기 때문에, 우선적으로 물을 먼저 이동시켜서 각 칸에 대해 물이 언제 도착하는 지에 대해 bfs를 실행한다.

bfs 2: 고슴도치의 이동

#고슴도치의 이동 수행
visited=[[False] * n_cols for _ in range(n_rows)]
while animal_queue:
    row,col,time=animal_queue.popleft()
    #목적지에 도달한 경우
    if (row,col)==(end_row,end_col):
        print(time)
        return
    #이전에 방문한 경우
    if visited[row][col]:
        continue
    visited[row][col]=True

    for dir in range(4):
        next_row=row+dy[dir]
        next_col=col+dx[dir]
        #범위를 벗어나는 경우
        if next_row < 0 or next_row>=n_rows or next_col<0 or next_col>=n_cols:
            continue
        #다음 좌표가 돌인 경우
        if board[next_row][next_col]=="X":
            continue
        
        #해당 자리에 물이 먼저 도착하는 경우에는 다음 좌표로 이동 불가능
        if time_map[next_row][next_col] <= time+1:
            continue
        animal_queue.append((next_row,next_col,time+1))

물의 이동을 먼저 수행한 다음, 고슴도치를 이동시킨다. 이때, 고슴도치가 해당 칸에 도착하는 시간과 물이 도착하는 시간을 비교해서 물이 먼저 도착하는 경우에는 고슴도치가 해당 칸으로 이동이 불가능하다.

Solution

from collections import deque
from math import inf
def solution():
    time_map=[[inf] * n_cols for _ in range(n_rows)]
    end_row,end_col=0,0
    water_queue,animal_queue=deque(),deque()
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    
    for row in range(n_rows):
        for col in range(n_cols):
            #출발점
            if board[row][col]=="S":
                animal_queue.append((row,col,0))
            #도착점
            if board[row][col]=="D":
                end_row,end_col=row,col
            #물이 있는 자리의 좌표
            if board[row][col]=="*":
                water_queue.append((row,col,0))
    
    #물의 이동 수행
    visited=[[False] * n_cols for _ in range(n_rows)]
    while water_queue:
        row,col,time=water_queue.popleft()
        
        #이전에 방문한 경우
        if visited[row][col]:
            continue
        visited[row][col]=True
        #물이 해당 좌표에 도달하는 시간
        time_map[row][col]=time
        

        for dir in range(4):
            next_row=row+dy[dir]
            next_col=col+dx[dir]
            #범위를 넘어서는 경우
            if next_row < 0 or next_row>=n_rows or next_col<0 or next_col>=n_cols:
                continue
            #다음 좌표가 돌인 경우
            if board[next_row][next_col]=="X":
                continue
            #물은 목적지 좌표에 도달할 수 없다.
            if board[next_row][next_col]=="D":
                continue

            water_queue.append((next_row,next_col,time+1))
    
    #고슴도치의 이동 수행
    visited=[[False] * n_cols for _ in range(n_rows)]
    while animal_queue:
        row,col,time=animal_queue.popleft()
        #목적지에 도달한 경우
        if (row,col)==(end_row,end_col):
            print(time)
            return
        #이전에 방문한 경우
        if visited[row][col]:
            continue
        visited[row][col]=True

        for dir in range(4):
            next_row=row+dy[dir]
            next_col=col+dx[dir]
            #범위를 벗어나는 경우
            if next_row < 0 or next_row>=n_rows or next_col<0 or next_col>=n_cols:
                continue
            #다음 좌표가 돌인 경우
            if board[next_row][next_col]=="X":
                continue
            
            #해당 자리에 물이 먼저 도착하는 경우에는 다음 좌표로 이동 불가능
            if time_map[next_row][next_col] <= time+1:
                continue
            animal_queue.append((next_row,next_col,time+1))

    print("KAKTUS")


if __name__ == "__main__":
    n_rows,n_cols=map(int,input().split())
    board=[list(input().strip()) for _ in range(n_rows)]
                
    solution()