TIL) 3055 탈출

이 글은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.

🐠 고슴도치와 물을 이동을 동시에 탐색

백준 3055 탈출 : https://www.acmicpc.net/problem/3055

💡 아이디어

• 지도를 저장해 놓은 그래프가 필요하다
• 물의 이동을 저장해놓을 queue가 하나 필요하고
  고슴도치의 이동을 저장해놓을 queue가 하나 필요하다.
  총 두 개의 queue를 가지고 탐색을 해야한다.
• day가 하나 증가할 때마다 물과 고슴도치를 동시에(물->고슴도치) 이동시켜야한다.
• 토마토를 풀 때 while문 안에서 day를 카운트하고 현재 queue의 길이 만큼 for문을 돌리는 방법을 여기에서도 똑같이 사용했다.
• 1일이 지나는 시점에서 물도 움직이고 고슴도치고 움직여야하기 떄문에 while 안에 물을 움직이는 for문과 고슴도치를 움직이는 for문이 모두 들어가야 한다.
• 물이 더 이상 움직일 수 없어도 고슴도치만 움직여서 D에 도착할 수 있기 때문에 while문의 종료 조건은 dochi queue가 비어있을 때로 정했다.

👀 나의 풀이

from collections import deque

R, C = map(int, input().split())
graph = []

for _ in range(R):
    graph.append(list(input()))

dochi = deque()
water = deque()

for i in range(R):
    for j in range(C):
        if graph[i][j] == '*':
            water.append((i, j))
        elif graph[i][j] == 'S':
            dochi.append((i, j))

day = 0
def bfs():
    global day
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while dochi:
        day += 1
        for _ in range(len(water)):
            y, x = water.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= C or ny >= R:
                    continue
                if graph[ny][nx] == '.':
                    graph[ny][nx] = day
                    water.append((ny, nx))

        for _ in range(len(dochi)):
            y, x = dochi.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= C or ny >= R:
                    continue
                if graph[ny][nx] == '.':
                    graph[ny][nx] = day
                    dochi.append((ny, nx))
                if graph[ny][nx] == 'D':
                    return day


answer = bfs()

if answer is None:
    print('KAKTUS')
else:
    print(answer)

D까지 도달하지 못하고 while문이 종료되면 dfs() 함수가 None을 반환하기 때문에

if answer is None:
    print('KAKTUS')
else:
    print(answer)

이렇게 출력했다.