[백준] 3055번 탈출

💡문제접근

• 고슴도치가 이동할 수 있는 경우를 나타내는 BFS 함수와 물이 넘칠 수 있는 경우를 나타내는 BFS 함수 두 개를 작성해서 문제를 해결했다.
• 다른 사람의 코드를 보지 않고 혼자서 해결하는 그 시간이 정말 고통스럽고 지옥같았다. 하지만 어떻게 풀어야할지 미리 생각해보고 코드의 흐름을 하나씩 천천히 알아가며 코드를 작성하는 부분에서 뿌듯함을 느꼈다.

💡코드(메모리 : 34240KB, 시간 : 76ms)

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

R, C = map(int, input().strip().split())
area = [list(input().strip()) for _ in range(R)]
visited = [[0 for _ in range(C)] for _ in range(R)]

water = deque()
animal = deque()

def flood():
    for _ in range(len(water)):
        x, y = water.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny]:
                # 만약 비어있는 곳이라면?
                if area[nx][ny] == ".":
                    area[nx][ny] = "*"
                    water.append((nx, ny))

def move():
    flag = False
    for _ in range(len(animal)):
        x, y = animal.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny]:
                # 만약 비어있는 곳이라면?
                if area[nx][ny] == ".":
                    flag = True
                    visited[nx][ny] = visited[x][y] + 1
                    animal.append((nx, ny))
                # 만약 비버의 소굴에 도달했다면?
                elif area[nx][ny] == "D":
                    return visited[x][y] + 1
    # 만약 고슴도치가 비버의 소굴로 이동할 수 없다면?
    if not flag:
        return "KAKTUS"

for i in range(R):
    for j in range(C):
        if area[i][j] == "S":
            animal.append((i, j))
        elif area[i][j] == "*":
            water.append((i, j))

while True:
    flood()
    res = move()
    if res:
       break
print(res)

💡소요시간 : 1h