1261 알고스팟 그래프
골4
다익스트라 알고리즘과 bfs 알고리즘 두가지 방법으로 모두 풀 수 있었다.
다만 나는 지금 다익스트라 알고리즘을 공부 중이므로 다익스트라로 풀었다.
bfs
bfs 로 푸는 방식은 그리디하게 풀게 된다.
- deque 을 만들어 앞 뒤 푸쉬를 가능하게 한다.
- 먼저 벽을 뚫지 않고 가는 길을 모두 탐색한다.
2-1 이 방법은 4방향 노드를 탐색하면서 0인 노드는 queue 의 앞에 넣고, 1인 노드는 뒤에 넣는다.
이렇게 하면 해당 코드는 0인 노드를 모두 탐색하고 1인 노드 탐색을 시작한다.
즉, 0인 노드를 모두 탐색하고 1인 노드를 탐색하면 최소의 벽을 부실 수 있다는 것을 보장하는 것이다. - N, M 까지 모두 탐색해서 노드가 N, M 이 되면 출력한다.
개인적으로 실제로 테스트를 볼 때는 위험한 방식일 수 있겠다는 생각이 든다. 내가 생각하지 못했던 부분을 간과하고 그리디하게 풀었다가 낭패를 볼 수 있다.
다익스트라
처음 문제를 봤을 때는 다익스트라를 생각하기 힘들 수 있다. 왜냐면 골드 이하의 다익스트라 문제는 항상 노드/간선 형태로 문제가 주어졌기 때문이다.
하지만 좌표에서도 다익스트라 알고리즘을 이용해 최소 경로를 찾아낼 수 있다.
좌표에서 상하좌우로 이동한다면 상하좌우의 간선이 존재한다고 생각하면 된다.
이 부분에서 조금만 다르게 생각한다면 다익스트라로 풀 수 있다.
또 다른 점은 2차원 좌표로 문제가 주어졌기 때문에, distance 결과 배열 또한 2차원 배열로 만들어주어야 한다는 것이다.
해당 부분을 주의하면서 다익스트라 알고리즘을 응용하면 쉽게 풀린다.
import heapq
INF = int(1e9)
M, N = map(int, input().split(" "))
graph = [list(map(int, input())) for _ in range(N)]
q = []
distance = [[INF for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def solution():
dijkstra((0,0))
print(distance[N - 1][M - 1])
def dijkstra(start):
heapq.heappush(q, (0, start))
distance[start[1]][start[0]] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now[1]][now[0]] < dist:
continue
for i in range(4):
nx = now[0] + dx[i]
ny = now[1] + dy[i]
if nx < 0 or ny < 0 or nx >= M or ny >= N:
continue
else:
cost = dist + graph[ny][nx]
if cost < distance[ny][nx]:
distance[ny][nx] = cost
heapq.heappush(q, (cost, (nx, ny)))
solution()
Author And Source
이 문제에 관하여(1261 알고스팟 그래프), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lky9303/1261-알고스팟-그래프저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)