출처 : https://www.acmicpc.net/problem/2206
from collections import deque
# n : 행 개수 , m :열 개수
n, m = map(int, input().split())
graph = [list(input()) for _ in range(n)]
# visited[0][x][y] : 벽을 안 부수고 (x, y)까지 최단거리
# visited[1][x][y] : 벽을 1회 부수고 (x, y)까지 최단거리
visited = [[[0] * m for _ in range(n)] for _ in range(2)]
def bfs(start_x, start_y) :
visited[0][start_x][start_y] = 1
move =[(0, 1), (0, -1), (1, 0), (-1, 0)]
to_visit = deque([(start_x, start_y, 0)])
while to_visit :
# z : (x, y)까지 오면서 벽을 부순 적이 있는지 저장 (0 : 안 부숨, 1 : 부숨)
x, y, z = to_visit.popleft()
if x == n - 1 and y == m - 1 :
return visited[z][x][y]
for dx, dy in move :
nx = x + dx
ny = y + dy
# 범위 벗어나면 방문하지 않음
if nx < 0 or nx >= n or ny < 0 or ny >= m :
continue
# 벽 부순 적이 없는 경우
if z == 0 :
# (nx, ny)에 방문한 적 없고 벽 없으면 그대로 이동
if visited[0][nx][ny] == 0 and graph[nx][ny] == '0' :
visited[0][nx][ny] = visited[0][x][y] + 1
to_visit.append((nx, ny, 0))
# (nx, ny)에 방문한 적 없고 벽 있으면 부수고 이동
elif visited[1][nx][ny] == 0 and graph[nx][ny] == '1' :
visited[1][nx][ny] = visited[0][x][y] + 1
to_visit.append((nx, ny, 1))
# 벽 부순 적 있는 경우
else :
# (nx, ny)에 방문한 적 없고 벽이 없으면 그대로 이동
if visited[1][nx][ny] == 0 and graph[nx][ny] == '0' :
visited[1][nx][ny] = visited[1][x][y] + 1
to_visit.append((nx, ny, 1))
return -1
print(bfs(0, 0))
'벽을 1번만 부술 때의 최단경로'를 구현하는게 어려웠다.
맵과 크기가 같은 2차원 리스트를 중첩한 3차원 리스트 visited 를 생성한다.
visited[0][x][y] 에는 벽을 부수지 않고 (x, y)까지의 최단경로, (0이면 방문한 적 없음)
visited[1][x][y] 에는 벽을 1번 부쉈을 (x, y)까지의 최단경로를 저장한다.
또한 방문한 좌표를 저장하는 큐 to_visit 에는 해당 좌표까지 이동하면서 벽을 부순 적이 있는지 여부를 추가로 저장한다.
이후의 코드에 대한 설명은 주석 참고
'알고리즘 문제 풀이' 카테고리의 다른 글
프로그래머스 롤케이크 자르기 (0) | 2023.01.25 |
---|---|
백준 10971번 : 외판원 순회 2 (Python) (0) | 2023.01.25 |
백준 1504번 : 특정한 최단 경로 (Python) (0) | 2023.01.02 |
백준 11057 : 오르막 수 (Python) (1) | 2022.12.31 |
백준 15649, 15650 : N과 M (1), (2) (Python) (0) | 2022.12.26 |
댓글