벽 부수고 이동하기 [백준 2206]

1. 문제 접근 방법

- 이 문제는 문제를 풀다가 막혀서 구글링해서 참고했다

  구글링을 통해서, visited 배열을 3차원 배열로 선언해서, 

  벽을 깬 케이스와 벽을 깨지 않은 케이스를 구분해서 접근할 수 있음을 알게 되었다. 

  이러한 접근법을 학습하게 되었고, 다른 문제를 푸는데 응용해봐야겠다. 

 

from collections import deque

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

board = [] 

visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


for i in range(N):
    
    row = input()
    tmp = []
    for j in range(M):
        tmp.append(int(row[j]))
    board.append(tmp)



def bfs(x, y, c):
    
    
    visited[x][y][0] = 1
    q = deque()
    q.append((x, y, c))


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

ans = bfs(0, 0, 0)
print(ans)