728x90
반응형
문제 바로가기
문제:
홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다. 홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다. 이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자. 인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.
입력:
2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000 1 ≤ Hx, Hy, Ex, Ey ≤ 1000 (Hx, Hy)≠ (Ex, Ey) 행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.
출력:
D (탈출 할 수 없다면, -1을 출력한다.)
풀이:
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m = map(int, sys.stdin.readline().split(" "))
# 시작
hx, hy = map(int, sys.stdin.readline().split(" "))
# 도착
ex, ey = map(int, sys.stdin.readline().split(" "))
graph = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(n)]
# 방문 배열, 0번째는 통과 1 번째는 벽부수고 통과
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def bfs(x, y):
Q = deque([(x, y, 0)])
visited[x][y][0] = 1
while Q:
dx, dy, wall = Q.popleft()
# 도착시
if dx == ex - 1 and dy == ey - 1:
return visited[dx][dy][wall] - 1
for a, b in move:
nx, ny = a + dx, b + dy
# 방문 안 한 지역 이면서 벽 안부셔도 가능
if 0 <= nx < n and 0 <= ny < m and not graph[nx][ny] and not visited[nx][ny][wall]:
Q.append((nx, ny, wall))
visited[nx][ny][wall] = visited[dx][dy][wall] + 1
# 방문 안 한 지역 이고, 벽 이면서, 아직 벽을 안 부셨음
elif 0 <= nx < n and 0 <= ny < m and graph[nx][ny] and not visited[nx][ny][wall] and not wall:
Q.append((nx, ny, wall + 1))
visited[nx][ny][wall + 1] = visited[dx][dy][wall] + 1
return -1
print(bfs(hx - 1, hy - 1))
예전에 풀었던 벽 부수고 이동하기 문제랑 똑같다
방문배열을 3차원 배열로 각 지점마다 벽을 부셨을경우와, 부시지 않았을 경우로 선언해주고
방문할때 벽부시기를 사용했는지 안 했는지를 들고 다니면서 bfs를 진행해주면 된다.
반응형
댓글