[백준 14923번] 미로 탈출

from collections import deque

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

n, m = map(int,input().split())

hx, hy = map(int,input().split())

ex, ey = map(int,input().split())

maze = [list(map(int,input().split())) for _ in range(n)]

visited = [[[0]*m for _ in range(n)] for _ in range(2)]

def bfs():
    
    visited[0][hx-1][hy-1] = 0

    queue = deque([(0,hx-1,hy-1)])

    while queue:
        v = queue.popleft()
        w, x, y = v[0], v[1], v[2]

        if x == ex -1 and y == ey -1:
            return visited[w][x][y]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if maze[nx][ny] == 0 and visited[w][nx][ny] == 0:
                    queue.append((w,nx,ny))
                    visited[w][nx][ny] = visited[w][x][y] + 1
                elif maze[nx][ny] == 1 and w == 0:
                    queue.append((w+1,nx,ny))
                    visited[w+1][nx][ny] = visited[w][x][y] + 1
    return -1

print(bfs())

이번 문제는 빈 칸과 벽으로 이루어진 2차원 배열에서 (hx,hy) 위치에서 시작하여 (ex,ey) 까지 도달하기 위해 이동해야 하는 최소 칸수를 구하되, 벽 하나를 부술 수 있다는 조건이 있는 문제이다.

 

처음에 이 문제를 접근했을 때는 이전에 풀었던 연구소 문제(https://woohyun-king.tistory.com/144)와 유사한 방식으로 필요한 로직을 분리하고, BFS와 완전 탐색(Brute Force)을 사용하여 풀이하였다.

 

하지만 N과 M의 크기가 컸을 뿐더러, 모든 벽들을 하나씩 부숴가면서 풀게 되면 시간복잡도가 너무 높아져 시간초과가 발생하게 된다.

 

따라서 각각의 벽을 하나씩 부숴가면서 모든 경우를 탐색하는 것이 아니라, 한 번의 BFS 탐색으로 최단거리를 구할 수 있어야 한다.

 

결국 풀이하지 못하고 유사한 문제인 '벽 부수고 이동하기'의 풀이를 참고하여 풀게 되었는데, 결국 이 문제의 핵심은 '벽을 이미 부순 상황'와 '벽을 아직 않은 상황'을 구분하여 값을 저장해나가는 방식으로 풀이해야 한다는 것이다.

 

원래는 visited 라는 방문여부를 확인하는 하나의 2차원 배열을 선언했지만 이번에는 벽을 이미 부쉈는지 여부를 확인하기 위해 2개의 2차원 배열을 만들어야 했고, 따라서 2xNxM 크기의 3차원 배열을 선언하였다.

 

if maze[nx][ny] == 0 and visited[w][nx][ny] == 0:
      queue.append((w,nx,ny))
      visited[w][nx][ny] = visited[w][x][y] + 1
elif maze[nx][ny] == 1 and w == 0:
      queue.append((w+1,nx,ny))
      visited[w+1][nx][ny] = visited[w][x][y] + 1

그리고 다음으로 이동하는 칸이 빈 칸(maze[nx][ny] == 0)이면서 아직 방문하지 않았다면(visited[w][nx][ny] == 0) 거리를 기록함과 동시에 queue에 넣어주고, 다음으로 이동하는 칸이 벽이지만(maze[nx][ny] == 1) 아직 벽을 부수지 않은 상황(w==0)이라면 벽을 넘은 상황의 2차원 배열에 거리를 기록함과 동시에 queue에 넣어주는 방식으로 풀이하였다.

 

if x == ex -1 and y == ey -1:
  return visited[w][x][y]

이렇게 한칸씩 이동하다가 탈출 위치(ex,ey)에 도달하게 되면 더 이상 이동하지 않고 곧바로 위치의 값을 반환하게 되면 그 값이 곧 최단거리가 될 것이다.

 

모든 경우의 수를 모두 구하는 방식이 아니라, 벽을 부순 상황과 부수지 않은 상황을 구별하여 푼다는 아이디어를 통해 풀 수 있는 문제였다. BFS는 queue 자료구조를 사용하기 때문에 한 칸씩 넓혀가며 탐색한다는 점을 다시 한번 리마인드할 수 있는 문제였다 :)