boj.kr/2206 벽 부수고 이동하기 (gold3) 파이썬 풀이

벽을 부수는 모든 경우의 수를 구하고 bfs를 여러번 돌려서 풀이한 결과 테스트 케이스에서는 통과했으나 전체 테스트 케이스에서 시간 초과 되었다.

 

정답 풀이 참고해 방문체크시 벽 부수기 기회 사용여부를 함께 저장하는 방식으로 bfs를 한번만 돌리도록 풀이한 결과 성공했다.

 

N, M = map(int, input().split())
graph = [input() for _ in range(N)]
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]

dy = (0, 0, -1, 1)
dx = (-1, 1, 0, 0)
from collections import deque
def bfs():
    dq = deque()
    dq.append((0, 0, 1, 1))
    visited[0][0][1] += 1
    while dq:
        (cy, cx, left, d) = dq.popleft()
        if cy == N-1 and cx == M-1:
            return d
        for i in range(4):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0<=ny<N and 0<=nx<M and visited[ny][nx][left] == 0:
                if graph[ny][nx] == '1' and left == 1:
                    dq.append((ny, nx, 0, d+1))
                    visited[ny][nx][0] += 1
                elif graph[ny][nx] == '0':
                    dq.append((ny, nx, left, d+1))
                    visited[ny][nx][left] += 1
    return -1
print(bfs())

 

벽을 부수고 이동하는 경우와 그렇지 않은 경우로 구분하여 방문체크해주어야 한다.