[백준] 3055 : 탈출 (파이썬)

BFS 문제

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

---

💡풀이코드 (성공 - BFS)

'''
.: 비어있는곳 (물 O, 고슴도치 O)
*: 물 (물 O, 고슴도치 X)
X: 돌 (물 X, 고슴도치 X)
D: 비버의 굴 (물 X, 고슴도치 O)
S: 고슴도치 위치 (물 O, 고슴도치 O)
'''

# 9:30 ~
import sys 
from collections import deque
r, c = map(int, sys.stdin.readline().split())
visited = [[False] * c for _ in range(r)]
visitedW = [[False] * c for _ in range(r)]
graph = []
S = None # 2) 좌표 사용 시 튜플 처음 선언
D = None
water = deque()

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

for i in range(r):
    l = list(map(str, sys.stdin.readline().strip())) # 1) split: 공백기준 / strip: 문자열 양쪽 공백 제거
    for j, s in enumerate(l):
        if s == 'S':
            S = (i, j)
        elif s == 'D':
            D = (i, j)
        elif s == '*':
            water.append((i, j))
    graph.append(l)


def water_spread():
    global water
    size = len(water)

    for i in range(size):
        wy, wx = water.popleft()

        for j in range(4):
            ny = wy + dy[j]
            nx = wx + dx[j]

            if 0 <= ny < r and 0 <= nx < c:
                if visitedW[ny][nx] == False:
                    visitedW[ny][nx] = True

                    if graph[ny][nx] == ".":
                        water.append((ny, nx))
                        graph[ny][nx] = "*"     
        
def bfs():
    global r, c, S

    is_possible = False
    queue = deque()
    cnt = 1
    queue.append((S[0], S[1], cnt))
    last = 0
    while queue:
        y, x, cnt = queue.popleft()

        if last != cnt:
            last = cnt
            water_spread() # 물 먼저 확장

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
    
            if 0 <= ny < r and 0 <= nx < c:
                if visited[ny][nx] == False:
                    visited[ny][nx] = True
                    if graph[ny][nx] == ".":
                        queue.append((ny, nx, cnt + 1))
                    elif graph[ny][nx] == "D":
                        is_possible = True
                        print(cnt)

    if is_possible == False:
        print("KAKTUS")
        return
        

bfs()

 

💡주요 로직

1. 물을 먼저 상, 하, 좌, 우로 확장시키기

이때, for문을 현재 queue의 크기만큼 돈다. (현재 시간에 존재하는 물의 갯수만큼)

만약 다음에 이동할 칸이 빈칸이라면 graph의 칸이 물임을 기록해준다.

 

2. 고슴도치 이동시키기

만약 다음에 이동할 칸이 빈칸이라면 고슴도치를 이동시킨다.

만약 다음에 이동할 칸이 물이라면 리턴시키는 코드는 작성할 필요가 없다.

• 만약 현재 분에 고슴도치가 상, 하, 좌, 우로 이동시키려는 칸이 전부 물이라면 리턴시키는 코드는 작성할 필요가 없다.
• 어차피, queue에 좌표를 못넣으므로 while queue:문이 종료될 것이기 때문이다.

또한, 매분마다 물처럼 고슴도치의 좌표를 graph에 기록하며 이동시킬 필요도 없다. (pop, add 등으로)

 

 

이때, 물을 확장시키는 함수를 매번 호출하지 않고, 분이 지났으면 확장시킨다. 

즉, cnt을 통해 현재 분을 판단한 후 물을 확장시키는 함수는 매 분마다 한번만 호출한다.