백준 3055 파이썬 python : 탈출 @@황소처럼 우직하게@@ 테스트케이스가 놓치고 있는 반례, 메모리초과, 시간초과 해결

제가 처음에 짠 코드에서 놓친 반례는

9 7
D . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . S

이런 단순한 반례였습니다. 

수정하고

시간초과가 났었는데 콜렉션의 디큐를 사용해줬죠.

또 수정하고

메모리초과가 났었는데 이차원 배열을 두개 사용했었죠.

그래서 

이중 배열 하나로 합쳤습니다.

큐에 일단 별들 위치 넣어주고, 마지막에 S위치 넣어줍니다.

그리고 그냥 bfs 돌리면 됩니다.

그러면 알아서 물 움직이고, 비버가 움직이는 시뮬레이션이 완성됩니다.

저의 정답 코드는 다음과 같습니다.

음수는 물이 도달하는 시간 * -1 값이고요, (이 값은 중요하진 않음)

양수는 비버가 가는데 걸리는 시간입니다.

결국 물이든 비버이든 . 인 곳에 갈 수 있는게 포인트입니다.

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

h, w = map(int, input().split())
mat = [[] for i in range(h)]
for i in range(h):
    ss = input().strip()
    for s in ss:
        mat[i].append(s)
q = deque()
for i in range(h):
    for j in range(w):
        if mat[i][j] == 'D':
            d_y = i
            d_x = j
        elif mat[i][j] == 'S':
            s_y = i
            s_x = j
        elif mat[i][j] == '*':
            q.append([i, j])
q.append([s_y, s_x])
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs():
    global q
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= nx < w and 0 <= ny < h:
                if mat[ny][nx] == 'X':
                    continue
                elif mat[y][x] == '*':
                    if mat[ny][nx] == 'D':
                        continue
                    elif mat[ny][nx] == '.':
                        mat[ny][nx] = -1
                        q.append([ny, nx])
                elif mat[y][x] == 'S':
                    if mat[ny][nx] == 'D':
                        mat[ny][nx] = 1
                        return
                    elif mat[ny][nx] == '.':
                        mat[ny][nx] = 1
                        q.append([ny, nx])
                elif mat[y][x] < 0:
                    if mat[ny][nx] == 'D':
                        continue
                    elif mat[ny][nx] == '.':
                        mat[ny][nx] = mat[y][x] - 1
                        q.append([ny, nx])
                elif mat[y][x] > 0:
                    if mat[ny][nx] == 'D':
                        mat[ny][nx] = mat[y][x] + 1
                        return
                    if mat[ny][nx] == '.':
                        mat[ny][nx] = mat[y][x] + 1
                        q.append([ny, nx])
bfs()
print(mat[d_y][d_x] if mat[d_y][d_x] != 'D' else "KAKTUS")

if 문이 많죠?

일반화된걸 찾을 수 있겠지만

그냥 생각나는대로 해줬습니다.