[백준/Python] 3055 탈출

문제링크

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

3055번: 탈출

---

 

코드

from collections import deque
from copy import deepcopy

def bfs_water(graph,water_idx):
    q = deque()
    for x,y in water_idx:
        q.append((x,y))
        time[x][y] = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=r or ny>=c:continue
            if graph[nx][ny] =='.':
                graph[nx][ny] = '#'
                time[nx][ny] = time[x][y] + 1
                q.append((nx,ny))

def bfs_hedgehog(x,y):
    graph[x][y] = 0
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=r or ny>=c:continue
            elif graph[nx][ny] =='.' or graph[nx][ny] =='D':
                if graph[x][y]+1< time[nx][ny]:
                    graph[nx][ny] = graph[x][y]+1
                    q.append((nx,ny))
            
r,c = map(int,input().split())
graph = [list(input()) for _ in range(r)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
water_idx = []
INF = float('inf')
time = [[INF for _ in range(c)] for _ in range(r)]
for i in range(r):
    for j in range(c):
        if graph[i][j]=='D':ans_x,ans_y = i,j
        elif graph[i][j]=='*':water_idx.append((i,j))
        elif graph[i][j]=='S':hedgehog_x,hedgehog_y = i,j

bfs_water(deepcopy(graph),water_idx)
bfs_hedgehog(hedgehog_x,hedgehog_y)
print('KAKTUS' if graph[ans_x][ans_y] =='D' else graph[ans_x][ans_y])

---

문제풀이

bfs를 물,고슴도치 따로 2번 돌렸다. 물이 차있는 곳은 고슴도치가 가지 못하므로 물의 이동을 먼저 bfs돌린다. 그리고 물의 좌표당 물이 차는 시간을 time리스트에 저장해둔다. 그리고 물의 시작좌표는 한 곳이 아닐 수 있다. water_idx에 넣어두고 bfs 시작할 때 한꺼번에 큐에 넣어준다.

그 다음 고슴도치이동을 bfs돌린다. 고슴도치가 가고자 하는 위치에 물이 차있으면 가지 못하므로 고슴도치가 가고자 하는 위치와 물이 차는 시간인 time을 비교하여 time보다 작으면 큐에 추가해준다.

bfs_water에는 graph의 복사본을 bfs_hedgehog에는 graph원본을 사용했다. 그러므로 bfs를 다 돌린 후 'D' 위치에 도착시간인 숫자가 아닌 'D' 가 저장되어 있다면 고슴도치가 가지 못하는 것이므로 KAKTUS를 출력한다.