백준 2206번 벽 부수고 이동하기

import sys
from collections import deque

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

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

graph = [list(map(int, input().strip())) for _ in range(N)]

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

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

def bfs(x, y, wall, visited, graph):
    queue = deque()

    queue.append((x, y, wall,)) # 큐에 현재 좌표하고 wall을 부시고 이동하는지 아닌지를 넣어준다.

    visited[x][y][wall] = 1

    while queue:
        x, y, wall = queue.popleft()

        if x == N - 1 and y == M - 1: # 도착하면 종료
            return visited[x][y][wall]

        for i in range(4): # 동서남북 탐색

            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= M: # 범위에 벗어날 경우 종료
                continue

            if graph[nx][ny] == 0 and visited[nx][ny][wall] == 0: # 아직 방문하지 않았을 경우 방문처리 (벽을 안부수고 갈 경우)
                queue.append((nx, ny, wall))
                visited[nx][ny][wall] = visited[x][y][wall] + 1

            if graph[nx][ny] == 1 and wall: # 벽을 부수고 갈 경우 
                queue.append((nx, ny, wall - 1))
                visited[nx][ny][wall - 1] = visited[x][y][wall] + 1

    return -1


print(bfs(0, 0, 1, visited, graph))

BFS에 대해서 다시 한번 이해하게 되는 계기가 되었다. 가면서 벽을 부수고 이동하면 되는 것이 었다. 처음에는 그냥 모든 벽을 다 부수면서 경우의 수를 찾는다고 생각하다가 그럴거면 알고리즘을 왜 배우나라는 생각이 들었다.

문제 해결은 간단했다. 일단 간 다음 벽을 부수고 간 경우를 이어서 넣어주면 된다. que특성상 선입 선출이기 때문에 가능하다.