[백준/14923] 미로 탈출 (Python)

Problem : https://www.acmicpc.net/problem/14923

14923번: 미로 탈출

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:13:26

 

---

 

문제 설명

 

 

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

 

 

입력 및 출력

 

입력

 

N M
Hx Hy
Ex Ey
N X M 행렬

 

2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000
1 ≤ Hx, Hy, Ex, Ey ≤ 1000
(Hx, Hy)≠ (Ex, Ey)
행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

 

출력

 

D (탈출 할 수 없다면, -1을 출력한다.)

 

입력 예시

 

5 6
1 1
5 6
0 1 1 1 0 0
0 1 1 0 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 0 0 1 1 0

 

출력 예시

 

11

 

 

---

 

풀이

 

최단 거리 경로 이동이므로 BFS를 이용하되, 단 한번 벽을 통과할 수 있다는 점을 감안하여 지팡이의 사용 여부까지 고려해야 한다. 즉 방문 배열 visited 는 (가로 x 세로 x 지팡이 사용여부)로 나누어지게 된다. 즉 이 문제의 간략화 버전이다.

 

2023.02.16 - [알고리즘 문제/백준] - [백준/16933] 벽 부수고 이동하기 3 (Python)

[백준/16933] 벽 부수고 이동하기 3 (Python)

 

주의할 점 : (x, y) 좌표계를 쓰는 것 같으면서 (r, c)를 따른다. 주의해서 코드를 작성하도록 하자.

 

 

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
cvt = lambda x : int(x)-1
N, M = map(int, input().split())
hx, hy = map(cvt, input().split())
ex, ey = map(cvt, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]

visited = [[[False]*2 for _ in range(M)] for _ in range(N)]
visited[hx][hy][0] = True
q = deque([(hy, hx, 0, 0)])
while q :
  x, y, move, wand = q.popleft()
  if (ey, ex) == (x, y) :
    print(move)
    exit()

  for k in range(4) :
    ax, ay = x + dx[k], y + dy[k]
    if -1 < ax < M and -1 < ay < N :
      if maps[ay][ax] == 0 and not visited[ay][ax][wand] :
        visited[ay][ax][wand] = True
        q.append((ax, ay, move+1, wand))
      if maps[ay][ax] == 1 and not wand and not visited[ay][ax][1] :
        visited[ay][ax][1] = True
        q.append((ax, ay, move+1, 1))
print(-1)

풀이 완료!