📚 1261 - 알고스팟
이해
시작하기에 앞서, 나는
다익스트라 알고리즘의 좋은 문제가 아니라고 생각하였기에bfs로 풀었다.
문제를 보자마자, 상하좌우를 보고 bfs, dfs 둘 중 하나로 풀어야겠다고 하였지만
조건 : 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하여라!
힌트 : 다익스트라
위와 같은 조건 및 힌트가 있어, dijkstra 알고리즘으로 풀어야 하는 줄 알고 구글링을 했지만, (그래프도 아닌 이차원에서 다익스트라를 푸는 문제는 처음이었다.)
이는 잘못된 생각이였다.
왜? 시간복잡도 및 더 간단하게 풀 수 있으니!
최소 몇 개 부수어야 한다고 했으니
dp와 유사하게 상하좌우 데이터들을 비교해가며 벽 부순 개수를 입력만 하면 된다.
방문 처리, 벽 부순 개수 저장 배열 : dist
길게 돌아올 때도 어차피 상하좌우 중 하나를 거쳐서 오기 때문에 상하좌우 중 가장 작은 값을 먼저 선택하여 체크한다. (이미 간 곳은 check 처리하여 다음에 다시 못오게 하기 위해, 삥 돌아와도 어차피 상하좌우로 오니, 오면 값이 더 커지거나 같다.)
| 0 | 1 | 1 | 0 |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 |
(0, 0) : 0
(0, 1) : 1 (현재 위치에 벽이 세워져 있다.)
(1, 1) : 1 (현재 위치에 벽이 세워져 있다.)
(0, 2) : 2
(1, 2) : min((1, 1), (0, 2)) : 1
(1, 3) : min((1, 2), (0, 3)) : 1
(2, 0) : (1, 0) + 1(현재 위치에 벽이 세워져 있다.)
(2, 1) : min((2, 0), (1, 1)) + 1 : 2
(1, 1)일 때 상하좌우로 가게 되는데, (1, 2), (2, 1)
(나머지는 이미 (0, 0)에서 방문한 상태)
여기서, 가장 작은 값을 선택해야한다.
(1, 2)는 0이므로 1이 되고, (2, 1)는 1이므로 2가 된다.
그러므로 위에서 말했던 상하좌우 중 가장 작은 값을 선택한다.
이용하여, (1, 2) 를 dist앞쪽에 넣고, (2, 1) 는 dist 뒷쪽에 넣고 각각 방문 처리를 한다.
코드를 보면 더 쉽게 이해가 될 것이라 생각한다.
소스
from collections import deque
import sys
read = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
m, n = map(int, read().split())
# 세로 : n, 가로 : m
graph = [list(map(int, read().strip())) for _ in range(n)]
dist = [[-1] * m for _ in range(n)]
def bfs():
q = deque()
# q에 넣고
q.append((0, 0))
# 0, 0에서 시작한다. (q에 0, 0과 0을 넣는다.)
# dist[0][0] = 0 시작 점은 한 번에 가니 상관없다.
dist[0][0] = 0
# q while 문
while q:
# x, y 좌표 점을 발급 받는다.
x, y = q.popleft()
# 상하좌우 돈다.
for i in range(4):
next_x = x + dx[i]
next_y = y + dy[i]
# 범위 안일 때
# 아직 방문하지 않은 곳이라면
# 만약 현재 그래프상 데이터 값이 0이라면
# 큐에 그냥 삽입한다. (대신에 가장 먼저 넣어야 한다.)
# 아니라면
# 큐에 삽입할 때, + 1을 한다.
if 0 <= next_x < n and 0 <= next_y < m and dist[next_x][next_y] == -1:
if not graph[next_x][next_y]:
dist[next_x][next_y] = dist[x][y]
q.appendleft((next_x, next_y))
else:
dist[next_x][next_y] = dist[x][y] + 1
q.append((next_x, next_y))
bfs()
print(dist[n - 1][m - 1])
