백준 3055 탈출(python)

문제

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

3055번: 탈출

---

BFS방식으로 문제에 접근했습니다. 물과 고슴도치 둘 다 움직이는데, 고슴도치는 물이 있는 곳으로 갈 수 없으니, 물을 먼저 움직여서 이차원 리스트에 표시해 두고, 그다음 고슴도치를 움직여 주었습니다. 물과 고슴도치 두 개의 큐를 사용하였습니다.

• 시작할 때 물의 위치와 고슴도치의 위치를 받아서 큐에 각각 넣어줍니다. 물은 여러 곳에 존재할 수 있습니다.
• 물이 갈 수 있는 곳을 찾아서 각 방향으로 움직여서 이차원 리스트에 표시해줍니다.
• 고슴도치가 있는곳을 큐에서 뽑아냅니다. 방문했는지 여부를 살펴보고 움직여 줍니다. 만약 그곳이 동굴이라면 시간을 출력해 줍니다.
• 고슴도치가 움질일때는 고슴도치가 움직일 수 있는 모든 경우를 가봐야 하기 때문에 큐의 사이즈만큼 반복해 줍니다.

 

---

소스코드 

import sys
from collections import deque

R, C = map(int, input().rstrip().split())

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

# 문자열 한 줄 이런식으로 하면 됨
arr = [list(map(str, input())) for _ in range(R)]
ch = [[0] * C for _ in range(R)]
gsdc = deque()  # 고슴도치
water = deque()  # 물
cnt = 0

for i in range(R):
    for j in range(len(arr[i])):
        if arr[i][j] == 'S':
            gsdc.append((i, j))
            ch[i][j] = 1
        elif arr[i][j] == '*':
            water.append((i, j))


while len(gsdc) != 0:
    cur_loop = len(water)
    for i in range(cur_loop):
        tmp = water.popleft()
        for j in range(4):
            yy = tmp[0]+dy[j]
            xx = tmp[1]+dx[j]
            if yy < 0 or xx < 0 or yy >= R or xx >= C or arr[yy][xx] == 'X' or arr[yy][xx] == 'D' or arr[yy][xx] == '*':
                continue
            if arr[yy][xx] == '.':
                water.append((yy, xx))
                arr[yy][xx] = '*'

    cnt += 1  # 시간 증가

    # 고슴도치 움직이는 로직
    cur_loop = len(gsdc)
    # 큐에 있는 모든 경우를 다 돌아 봐야함
    for _ in range(cur_loop):
        cur = gsdc.popleft()
        for i in range(4):
            yy = cur[0]+dy[i]
            xx = cur[1]+dx[i]
            if yy < 0 or xx < 0 or yy >= R or xx >= C or arr[yy][xx] == 'X' or arr[yy][xx] == '*':
                continue
            if arr[yy][xx] == '.' and ch[yy][xx] == 0:
                gsdc.append((yy, xx))
                ch[yy][xx] = 1
            elif arr[yy][xx] == 'D':
                print(cnt)
                exit()

print("KAKTUS")