파이썬 백준 3055 탈출

import sys input = sys.stdin.readline from collections import deque r, c = map(int, input().split()) T = [] que = deque() for i in range(r) :     T.append(list(input()))     for j in range(c) :         if T[i][j] == '*' :             que.append([i, j, 0, '*']) for i in range(r) :     for j in range(c) :         if T[i][j] == 'S' :             que.append([i, j, 0, 'S']) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] done = False while que :     a, b, t, f = que.popleft()     for i in range(4) :         x = a + dx[i]         y = b + dy[i]         if 0 <= x < r and 0 <= y < c :             if f == '*' and (T[x][y] == '.' or T[x][y] == 'S') :                 T[x][y] = f                 que.append([x, y, t + 1, f])             elif f == 'S' and T[x][y] == '.' :                 T[x][y] = f                 que.append([x, y, t + 1, f])             elif f == 'S' and T[x][y] == 'D' :                 done = True                 print(t + 1)                 break     if done :         break if not done :     print('KAKTUS')

입력받은 필드 정보대로 2차원 행렬을 작성한다. 물은 큐에 넣어준다.

고슴도치는 물이 찰 예정인 칸에 못가므로 (=같은 시간에 물과 고슴도치가 둘다 빈칸에 갈 수 있다면 물이 먼저 가므로) 물을 큐에 다 넣은 뒤에 큐에 넣는다.

이런 순서로 BFS를 실행하면 매 시간 큐 안에서 고슴도치는 물 뒤에 있으므로 항상 물보다 늦게 처리된다.

BFS 안에서 물은 인접한 빈칸 혹은 고슴도치를 물로 만들고, 고슴도치는 인접한 빈칸을 고슴도치로 만든다(?)

고슴도치의 인접한 칸 중에 비버굴이 있다면 다음 시각에 탈출에 성공하므로 현재시각 + 1을 출력하고 break한다.

탈출에 성공할 루트가 없다면 전부 물이 되고 que가 빌때까지 while문이 돈 뒤 KAKTUS를 출력한다.