백준 - 벽 부수고 이동하기(2206)

문제 링크 ▶︎ 백준 벽 부수고 이동하기 2206

문제 전략

이 문제는 BFS 문제이다.

graph를 탐색하면서 1번은 벽을 깨고 이동할 수 있다는 것을 보고 visit를 3차원으로 만드는 것이 중요하다.
즉, 기존의 2차원 visit을 2개로 겹쳐두고 첫 visit에서 bfs로 진행하다가 벽을 부수게 되면 다음 visit에서 진행한다는 개념이다.

BFS 함수에서 3차원 visit 그래프를 만들고, Queue에는 좌표(x,y)와 벽을 부술 기회(t)를 넣는다. (0,0)에서 시작되고 처음에는 벽을 부술 기회가 1번 있기 때문에 (0,0,1) 을 넣고 시작한다.
만약 t==1 이라면, 즉 벽을 부술 기회가 남았다면 벽을 만났을 때 부수고 t를 0으로 바꾼 후 다른 visit에서 진행하고 벽을 만나지 않으면 해당 visit에서 계속 진행한다.

만약 도착지점에 도달하지 못하고 while 문을 빠져나오게 되면 -1을 리턴, 도착지점에 도달하게 되면 해당 visit 값을 리턴한다.

코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())  # n행 m열
graph = [list(map(int, input().strip())) for _ in range(n)]

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

def bfs(t):
    visited = [[[0,0] for _ in range(m)] for _ in range(n)]
    visited[0][0][t] = 1
    q = deque([(0, 0, t)])  # (y, x, 벽 부술 남은 기회)
    while q:
        y, x, t = q.popleft()

        if y == n - 1 and x == m - 1:
            return visited[y][x][t]

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if graph[ny][nx] == 0 and visited[ny][nx][t] == 0:
                visited[ny][nx][t] = visited[y][x][t] + 1
                q.append((ny, nx, t))
            if graph[ny][nx] == 1 and t == 1:
                visited[ny][nx][t-1] = visited[y][x][t] + 1
                q.append((ny,nx,t-1))

    return -1

print(bfs(1))

개선 사항

3차원 배열 visit을 사용하는 방법말고 다른 방법도 고민.