[Python]3055. 탈출

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

3055번: 탈출

---

 

물이 미리 차오르는 시간을 구한다음, 고슴도치를 움직이도록 한다.

from collections import deque
 
def bfs(lst):
    global row, col
    queue = deque()
    for i in lst:
        queue.append(i)
        flooding_time[i[1]][i[2]] = 0
 
    while queue:
        cha, curr_y, curr_x = queue.popleft()
        for d in dr:
            next_y, next_x = curr_y+d[0], curr_x+d[1]
            if 0<=next_y<row and 0<=next_x<col:
                if cha == '*': # 물이 queue에 있을 때
                    if MAP[next_y][next_x] == '.' and flooding_time[next_y][next_x] == -1:
                        flooding_time[next_y][next_x] = flooding_time[curr_y][curr_x]+1
                        queue.append(('*', next_y, next_x))
                else: # 고슴도치가 queue에 있을 때
                    if (flooding_time[curr_y][curr_x]+1 < flooding_time[next_y][next_x]) or (flooding_time[next_y][next_x]==-1 and MAP[next_y][next_x] == '.'):
                        flooding_time[next_y][next_x] = flooding_time[curr_y][curr_x] + 1
                        queue.append(('S', next_y, next_x))
                    
                    # 고슴도치가 이동하다가 'D'에 도달하면
                    if MAP[next_y][next_x] == 'D' and flooding_time[next_y][next_x] == -1:
                        flooding_time[next_y][next_x] = flooding_time[curr_y][curr_x] + 1
                        return
 
dr = ((-1, 0), (1, 0), (0, -1), (0, 1))
row, col = map(int, input().split())
MAP = [list(input()) for _ in range(row)]
dic = {'D':[], 'S':[], '*':[]}
 
# D, S, * 의 위치를 찾아서 딕셔너리에 저장한다.
for r in range(row):
    for c in range(col):
        if MAP[r][c] == 'D':
            dic['D'].append((r, c))
        if MAP[r][c] == 'S':
            dic['S'].append(('S', r, c))
        if MAP[r][c] == '*':
            dic['*'].append(('*', r, c))
 
# 물이 차오르는 시간 계산
flooding_time = [[-1]*col for _ in range(row)]
 
bfs(dic['*'])
bfs(dic['S'])
 
if flooding_time[dic['D'][0][0]][dic['D'][0][1]] == -1:
    print('KAKTUS')
else:
    print(flooding_time[dic['D'][0][0]][dic['D'][0][1]])
 
'''
# input
10 15
........X......
..XXXXX.X.*....
X.....X.X..*...
.X.S..X.X......
D.X...X.XXXXXXX
.X....X........
.X....X.XXXXXXX
.XXXXXX.X......
........X......
XXXXXXXXX...*..

# output
30
'''