[백준] 3055번 탈출 (by Python)

문제

BFS 문제에서 길을 찾아가는 주체뿐만 아니라 갈 수 없는 길까지 큐를 이용해서 업데이트해주어야 하는 문제. 생각이 부족한 탓에 시간 초과 + 디버깅의 헬파티로 힘든 시간을 보냈다... 시간 초과로 문제를 원망하고 파이썬을 원망했지만 프로그래머로서 올바른 자세는 내 머리를 원망해보자는 생각....

 

풀이

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

r, c = map(int, input().split())
forest = [list(input().strip()) for _ in range(r)]
steps = [(1, 0), (0, 1), (-1, 0), (0, -1)]
answer = 0
flag = True
q = deque()

for i in range(r):
    for j in range(c):
        if forest[i][j] == '*':
            q.append(('*', i, j))

for i in range(r):
    for j in range(c):
        if forest[i][j] == 'S':
            forest[i][j] = 0
            q.append((0, i, j))

while q and flag:
    what, y, x = q.popleft()
    for step in steps:
        n_x, n_y = x + step[0], y + step[1]
        if 0 <= n_x < c and 0 <= n_y < r:
            if what == '*':
                if forest[n_y][n_x] not in ['*', 'X', 'D']:
                    forest[n_y][n_x] = '*'
                    q.append(('*', n_y, n_x))
            else:
                if forest[n_y][n_x] == '.':
                    forest[n_y][n_x] = what + 1
                    q.append((what + 1, n_y, n_x))
                elif forest[n_y][n_x] == 'D':
                    answer = what + 1
                    flag = False
                    break

print("KAKTUS" if flag else str(answer))

내가 겪은 코드 수정의 단계는 다음과 같다.

 

1. 물이 퍼지는 큐와 고슴도치가 길을 찾아가는 큐를 분리했던 것을 합쳐주기 

→ 시간 초과 문제 해결! 정말 필요한 변수인지 스스로에게 한 번 더 물어보자.

 

2. 시간 측정 방식을 바꿈

→ 원래는 큐를 pop한 값이 물에서 고슴도치로 바뀌는 순간마다 count를 +1씩 해주는 방식을 취했으나, 물이 다 퍼지고 났을 때 올바르게 count되지 않는다는 것을 깨닫고 forest에 걸린 시간을 표시해주는 방식으로 변경했다.

 

3. 처음 물이 한 개가 아니라는 것을 깨닫다

→ 조금이라도 시간을 줄이고 싶은 마음에 while loop으로 '*'을 찾자마자 바로 break하는 방법으로 물의 위치를 큐에 넣었으나 'D'와 'S'가 1개씩이지 물이 1개라는 언급은 문제에 없다. 그래서 찾는대로 집어넣도록 코드를 바꾸었다.

 

지난한 디버깅의 과정을 겪었지만, 코드의 문제점을 발견할 때마다 드는 생각은 '조금만 더 집중했으면 이렇게 풀지 않았을텐데' 였다.

설렁설렁 코딩하고 오류가 많다고 속상해하지 말고 코딩하는 이상, 집중할 것.