[BFS] 백준 3055번 탈출 with Python3

illustrated by GMG

 

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

3055번: 탈출

문제

 

내 풀이

# R C / 행열
# D 고슴도치 / S 비버굴 / *물 / . 맨땅 / X 돌

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

row, col = map(int, input().split())
field = []
for i in range(row):
    field.append(list(input().rstrip()))

visited = [[0] * (col) for _ in range(row)]


Q = deque()
rockQ = deque()

for i in range(row):
    for j in range(col):
        if field[i][j] == 'S':
            start_row, star_col = i, j
        # elif field[i][j] == 'D':
        #     end_row, end_col = i, j
        elif field[i][j] == '*':
            rockQ.append([i, j])
        # elif field[i][j] == 'X':
        #     visited[i][j] = 1


Q.append([start_row, star_col])
field[start_row][star_col] = 1


# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
count = 0


def bfs():
    global count

    while Q:

        # print(f'ini:{field}')

        # 물 이동
        length = len(rockQ)
        for _ in range(length):
            [rock_x, rock_y] = rockQ.popleft()

            for i in range(4):
                rx = rock_x + dx[i]
                ry = rock_y + dy[i]

                # or type(field[rx][ry]) == int):
                if (0 <= rx < row) and (0 <= ry < col) and field[rx][ry] == '.':

                    # print(f'나는 x:{rx} ry나는 y:{y}')
                    rockQ.append([rx, ry])
                    field[rx][ry] = '*'

        count += 1
        # print(f'water:{field}')

        # 고슴도치 이동
        length2 = len(Q)
        for _ in range(length2):
            [x, y] = Q.popleft()
            visited[x][y] = 1

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if (0 <= nx < row) and (0 <= ny < col) and visited[nx][ny] == 0:

                    if field[nx][ny] == 'D':
                        # field[nx][ny] = field[x][y] + 1
                        print(count)
                        exit()

                    elif field[nx][ny] == '.':
                        visited[nx][ny] = 1
                        # print(f'나는 x:{nx} / 나는 y:{y}')
                        Q.append([nx, ny])
                        # field[nx][ny] = field[x][y] + 1
        # print(f'after:{field}')
        # print()


bfs()

print('KAKTUS')

해설

아무것도 안보고 구현했을때 미로 탐색 식으로 이전 값을 더하는 방식으로 구현했엇다. 그 흔적들은 주석으로 볼 수 있다.

 

이 방식의 문제점은 고슴도치가 지나오면서 바꾼 좌표의 값들이 물이 못넘어가게하는 방파제 역할을 하게 된다는 점이다. 

 

이를 해결하기위해 count를 넣었다. 덕분에 연산 자체가 깔끔해졌다.

 

막혔을 때 힌트를 얻기 위해 https://kspsd.tistory.com/14#comment12834435 를 참고했다.

정답 풀이

X

출처:

 

해석