💎 문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
💎 입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
💎 출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
💎 풀이 방법
단순한 BFS 문제라고 생각했는데 생각보다 까다로운 조건이 하나 있는 그래프 탐색 문제이다. 보면 문제 조건에 이동하는 도중 한 개의 벽을 부수고 이동할 수 있다고 했기 때문에 이를 고려하여 최소 이동하는 거리를 구하는 것이다. 따라서 더 복잡하게 생각할 수 있어 어려웠던 것 같다.
하지만! 정말 문제를 풀다 보니 확인한 것은 기존 BFS로 그대로 풀되 만약 그 장소가 벽을 뚫어야 갈 수 있는지 아니면 그냥 이동이 가능한지로 나눠서 풀면 된다는 생각으로 접근하면 다른 그래프 탐색 문제와 비슷한 느낌이다!!
이는 3차원 배열로 문제를 풀어 벽을 뚫은 여부를 0, 1로 체크하여 벽을 뚫고 이동한 경우는 1로 체크해 두어 이 후 이동에는 벽을 뚫을 수 없도록, 그리고 아직 뚫지 못했을 때는 이동할 수 있는 구간이 0에서 1로 바꾸어 방향을 나아갈 수 있도록 하면 되었다.
visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]
visited[0][0][0] = 1따라서 위와 같이 visited 배열을 3차원 배열로 선언하여 출발하는 지점을 기준으로 4방향을 탐색하고 벽을 뚫고 온 경우와 뚫고 오지 않은 경우를 고려하면서 최단 경로를 구할 수 있다.
그리고 잊지 말고 혹시 모르니 반복문을 통한 입력은 sys 모듈 readline을 이용하여 입력받도록 하자!!
if wall[Y][X] == '0' and visited[Y][X][z] == 0:
visited[Y][X][z] = visited[y][x][z] + 1
q.append((Y, X, z))
elif wall[Y][X] == '1' and z == 0:
visited[Y][X][1] = visited[y][x][0] + 1
q.append((Y, X, 1))위와 같이 만약 이동하는 방향이 0이라면 정말 그대로 원래 하듯이 이동하는 장소로 경로에 1을 더해주어서 계산하고, 1일 경우에는 기존에 벽을 뚫었는지 확인하고 이동한 경로에는 벽을 뚫은 표시와 함께 큐에 push 해서 계산한다!!
💎 전체 코드
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
wall = [list(map(str, input().rstrip())) for _ in range(N)]
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
def bfs():
q = deque()
q.append((0, 0, 0))
visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]
visited[0][0][0] = 1
while q:
y, x, z = q.popleft()
if y == N - 1 and x == M - 1:
return visited[y][x][z]
for i in range(4):
Y = y + dy[i]
X = x + dx[i]
if Y >= N or Y < 0 or X >= M or X < 0:
continue
if wall[Y][X] == '0' and visited[Y][X][z] == 0:
visited[Y][X][z] = visited[y][x][z] + 1
q.append((Y, X, z))
elif wall[Y][X] == '1' and z == 0:
visited[Y][X][1] = visited[y][x][0] + 1
q.append((Y, X, 1))
return -1
print(bfs())💎 고민
그래프 탐색의 BFS를 파이썬으로 풀다보니 확실히 파이썬은 문자열과 배열 계산에서 효율적이라는 점을 다시금 느끼는 것 같다. 그래프 탐색이 평범하게 나올 확률이 낮다라는 생각을 하면서 어떠한 특수 조건이 그래프 탐색에 어떻게 영향을 미치는지 파악할 수 있도록 문제를 접근하도록 해야겠다!!
화이팅~!
