백준 2206 문제 분석

🐒 벽 부수고 이동하기

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

✍ 나의 풀이

from collections import deque
import sys


input = sys.stdin.readline

N, M = map(int, input().split())


visited = [ [ [0]*2 for _ in range(M) ]for _ in range(N)]

matrix = []
for _ in range(N):
    matrix.append(list(map(int,input().rstrip())))

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

def bfs():
    q = deque()
    q.append((0,0,0))
    visited[0][0][0] = 1
    while q:
        x, y, z = q.popleft()
        if x == N-1 and y == M-1:
            return visited[x][y][z]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if matrix[nx][ny] == 1 and z == 0:
                    visited[nx][ny][1] = visited[x][y][0] + 1
                    q.append((nx,ny,1))
                elif matrix[nx][ny] == 0 and visited[nx][ny][z] == 0:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    q.append((nx,ny,z))
    return -1

print(bfs())

처음에는 벽을 만나면 방문기록을 복사해서 그속에서 bfs를 돌리는 방법을 생각하고 구현을 했는데 구현중에 문제도 생겼도 해결했으나 시간초과가 발생했다.

그래서 검색을 통해 삼차원배열에 방문기록을 저장하는 풀이를 찾았다.
참고한 블로그

🧠 문제 이해

벽을 만나기 전까지는 vistied[x][y][0]에 이동횟수를 기록하다가
벽을 한번 만나면 visited[x][y][1]에 이동횟수를 기록하기 시작한다.
이렇게 이차원 배열이 아닌 삼차원 배열로 이동횟수를 투트랙으로 기록할 수 있으므로 먼저 matrix[x][y]을 탐색하는 쪽의 이동횟수를 출력하고 전체를 탐색해도 matrix[x][y]탐색에 실패하면 -1을 출력한다.