3055: 탈출

풀이 시간

• 35 m

구현 방식

• bfs를 돌 때, 현 시점을 기준으로 queue에 들어있는 node들을 한번에 처리해줘야함
• 중복 제거를 위한 visit 리스트도 매 stage마다 초기화해주어야함
• "고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다."
  -> 이 조건을 토대로 먼저 물이 퍼지는 부분을 구현해준 다음에 고슴도치를 이동시켜줘야함
• node에 x, y, cnt를 넣어줘서 최소 시간을 기록해줌

소스 코드

import sys
from collections import deque

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs():
    queue = deque([])
    x, y = src
    queue.append([x, y, 0])

    while queue:
        # 물 퍼짐
        for _ in range(len(water)):
            x, y = water.popleft()
            for i in range(4):
                nx = x + dx[i]; ny = y + dy[i]
                if 0 <= nx < R and 0 <= ny < C:
                    if board[nx][ny] == '.':
                        board[nx][ny] = '*'
                        water.append([nx, ny])

        visit = [[False] * C for _ in range(R)]
        for _ in range(len(queue)):
            x, y, cnt = queue.popleft()
            if x == dest[0] and y == dest[1]:
                print(cnt)
                return
            for i in range(4):
                nx = x + dx[i]; ny = y + dy[i]
                if 0 <= nx < R and 0 <= ny < C:
                    if (board[nx][ny] == '.' or board[nx][ny] == 'D') and not visit[nx][ny]:
                        queue.append([nx, ny, cnt + 1])
                        visit[nx][ny] = True
        
    print('KAKTUS')

R, C = map(int, sys.stdin.readline()[:-1].split())
board = []
dest = []; src = []; water = deque([])
for r in range(R):
    tmp = list(sys.stdin.readline()[:-1])
    for c in range(C):
        if tmp[c] == 'D':
            dest = [r, c]
        elif tmp[c] == 'S':
            src = [r, c]
        elif tmp[c] == '*':
            water.append([r, c])
    board.append(tmp)

bfs()

결과

• 탐색 문제는 노드를 중복하여 방문하는 경우를 잘 제거헤주는 게 포인트인 것 같다