[WEEK03] 23일차. 탈출

백준 3055 탈출

문제 링크

혼자 힘으로 풀려고 했는데 오류가 계속 발생해서 블로그를 참고하였다.

블로그 링크

이 풀이는 물의 퍼짐과 고슴도치의 이동을 따로 bfs로 만들지 않고 하나의 bfs로 만든 것이 특징이다.

주의할 점은 순서를 고려하지 않고 그냥 for문을 돌리면서 q에 i,j 인덱스를 넣을 경우
고슴도치가 움직이기 전에 물이 먼저 퍼져서 고슴도치가 움직일 수 없는 상황이 발생하기 때문에
고슴도치 위치인 'S'를 먼저 찾아서 큐에 넣고 그 다음 물의 위치인 '*'를 큐에 넣어서 고슴도치를 먼저 이동하게 해주었다.

코드

from sys import stdin
from collections import deque
input = stdin.readline

R, C = map(int, input().split())
_map = []
dist = [[0]*C for _ in range(R)]

def bfs(Dx, Dy):
    while q:
        x, y = q.popleft()
        if _map[Dx][Dy] == 'S':
            return dist[Dx][Dy]
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < R and 0 <= ny < C:
                if (_map[nx][ny] == '.' or _map[nx][ny] == 'D') and _map[x][y] == 'S':
                    _map[nx][ny] = 'S'
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
                elif (_map[nx][ny] =='.' or _map[nx][ny] =='S') and _map[x][y] == '*':
                    _map[nx][ny] = '*'
                    q.append((nx, ny))
    return "KAKTUS"

q = deque()

for i in range(R):
    _map.append(list(input().rstrip()))
    for j in range(C):
        if _map[i][j] == 'S':
            q.append((i, j))
        elif _map[i][j] == 'D':
            Dx, Dy = i, j

for i in range(R): # 물을 나중에 큐에 넣음(물이 먼저 퍼지면 고슴도치가 못 움직임)
    for j in range(C):
        if _map[i][j] == '*':
            q.append((i,j))

print(bfs(Dx, Dy))