문제

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

나의 코드 (디버깅 4시간 ㅠㅠ.)

"""
1. 아이디어
일단 문제에 명시된 '고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 
즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.' 조건을 보고
큐에 물부터 다 넣고, 고슴도치를 넣어야 하는 것을 확인할 수 있다. 그 이후는 bfs를 돌리면
되는데 이때 'D', 즉 도착지점을 만났을때 min()함수를 해줘야 한다. (이거땜에 4시간걸림;; 아니근데 안해줘도 답 다나오던데 정밀성이 요구되는구나.. )
왜냐하면 그래프에 장애물(물)이 계속 추가되는 상황이기 때문에 단순히 고슴도치가 이동하는 것이
최단거리를 보장해주지 못하기 때문이다.

2. 시간복잡도
O(NM)인데 중간에 도착지점을 만날때 min()연산을 한번 하므로 약간은 더 걸릴 것이다.
"""

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

n, m = map(int, input().split())
maps = [ list(input().rstrip()) for _ in range(n) ]
answer = 1e9

q = deque()

""" 
'고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.'
라는 조건이 있으므로 물을 먼저 BFS 탐색을 시키고 그 다음 고슴도치를 BFS 탐색시키면 될 것이다. 
"""
for i in range(n):
    for j in range(m):
        if maps[i][j] == '*':
            q.append((i, j))


for i in range(n):
    for j in range(m):
        if maps[i][j] == 'S':
            maps[i][j] = 0 # 고슴도치가 이동하는 시간을 세기 위해 고슴도치의 위치를 0으로 초기화 해준다.
            q.append((i, j))

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

while q:
    px, py = q.popleft()

    for k in range(4):
        mx = px + dx[k]
        my = py + dy[k]

        if 0 <= mx < n and 0 <= my < m:
            if maps[mx][my] == '.': # 만약 이동할 곳이 비어있는 곳이라면
                if maps[px][py] == '*': # 현재 BFS를 탐색하고 있는 것이 물이라면
                    maps[mx][my] = '*' # 이동할 곳을 물로 채워 준다.
                    q.append((mx, my))
                else: # 현재 BFS를 탐색하고 있는 것이 고슴도치 라면
                    maps[mx][my] = maps[px][py] + 1 # 이동할 곳을 +1을 해줌으로써 시간을 세어준다.
                    q.append((mx, my))

            elif maps[mx][my] == 'D': # 도착지점에 도착했다면
                if maps[px][py] != '*': # 현재 BFS를 탐색하고 있는 것이 물이 아니라면 = 고슴도치 라면
                    """ 시간을 세고 정답 변수에 값을 대입한 후 BFS를 종료한다.
                    이때, min()을 해주는 이유는 min()을 안해주면 이 문제는 그래프가 시간에 따라 장애물이 추가되는 상황이기 때문에 
                    단순히 고슴도치가 움직여서 도착하는게 최단거리 임을 보장해줄 수 없기 때문이다. """
                    answer = min(answer, maps[px][py] + 1)
                    break

if answer == 1e9:
    print("KAKTUS")
else:
    print(answer)

    

느낀점

세상에 알고리즘 고수는 많다고 느꼈다.. 테스트 케이스 다 통과하고 게시판에 있는 반례 다 통과했는데 왜 틀리나 싶었는데 알고리즘 톡방에 고수분이 바로 문제점을 지적해주셨다! (answer = min(answer, maps[px][py] +1) 이부분..
이거 보고 아직 멀었구나 싶었다 ㅠ

4월 15일 추가)

다시 한번 푸는 과정에서
if maps[px][py] != '': 이부분을
if maps[px][py] >= 0:으로 풀었는데 안 돼서 헤매었다.
계속 생각해보니 물이 확장되는, 즉 maps[px][py]가 물인 경우에는 >= 0하고 연산을 하게되면 str과 int의 연산이 되기 때문에 에러가 났던 것이었다.
그래서 if maps[px][py] != '' 이렇게 써줘야 하는 것이다.

그리고 answer = min(answer, maps[px][py] + 1) 이 부분도 다시 한번 봐야한다.
주석에 나와있는 것 처럼 이 문제는 그래프가 시간에 따라 장애물이 추가되는 상황이기 때문에 단순히 고슴도치가 움직여서 도착하는게 최단거리 임을 보장해줄 수 없기 때문에 min()을 해줘야 하는 것이다.