먼저 이건 데이크스트라(dijkstra)씨가 만들었습니다
그리고 알고리즘 이름도 데이크스트라(다익스트라)여서 보통 함수이름을
def dijkstra():
pass이런식으로 구성하는데 본인 기준 dijkstra 저거 스펠링이 괴랄해서
다른분들 코드 참고할 때 조금 보기 힘들었습니다..
저는 코테충이기 때문에 코테에서 쓰일 수 있는 '기본' 데이크스트라 활용문제 2개를 소개할게요
이미 알고계신 분들은 함 풀고오시죠
모르시면 쭉내리십쇼
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
-----스포방지-----
이거 2개가 제가 함 본결과 대표적인 유형이라고 생각을 좀 하구요
for문으로 최소거리인 노드를 찾아서 탐색하는 그냥 데이크스트라
그리고 heap을 써서 최소값을 빨리 뽑아내서 조금더 좋은 데이크스트라 가 있습니다
근데 그냥 heap 쓰세요
힙 자료구조 모르시는 분들은
https://velog.io/@tk050501/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-heapq
여기 참고하시구요
힙 찾아보기 귀찮으신 분들을 위해 간단하게 요약하자면 O(logN) == (상당히빠름) 의 속도로 제일 작은 수를 뽑아내는 자료구조입니다
그냥 그렇게만 아시고 나중에 백준 최소힙, 최대힙 이런거 풀어보세요 이거매우중요함 최소값 빨리뽑는 테크닉은 그리디에서도 쓰이고 그럽니다
그럼 데이크스트라로 돌아와서
먼저 2개 유형을 간단하게 구분을 해보면 그냥 입력을 이런식으로 주는 노드와 노드사이의 데이크스트라
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6그리고 입력을 이런식으로 주는 2차원배열 데이크스트라 가 있겠네요
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5근데 2차원 데이크스트라 이건 제가 문제 쭉 봤는데 거의없었습니다 그냥 혹시나 모르니까 알아두십쇼
일단 데이크스트라 알고리즘 동작 순서부터 한번 알아볼게요
- 처음 시작하는 내가 있는 위치의 비용을 0으로 잡고(내 현재위치는 비용이 0이니까) heap에 넣는다
- heap에서 비용이 가장 작은 원소를 꺼내서
distance에 원래 있던 비용 vs heap에서 방금 꺼낸 비용 + 여기까지 오기 위해 들인 비용 비교해서 더 작은걸 distance에 추가해줌
- 2번을 무겐루프 해줌
이게 다구요 그냥 님들이 이거 보신다는건 아마 BFS 이런거 다 하셨다는걸텐데 BFS 감성으로 그냥 코드 쫘라락 외워서 골수쯤에서 코드 뽑아서 치면 잘풀릴듯 하네요
# PROBLEM - 최단경로
# TIER - G4
# NUMBER - 1753
# DATE - 2022-08-11 20:08
# IDEA - 데이크스트라의 근본
import sys
import heapq
N, M = map(int, input().split())
INF = int(10e9) # 10억
graph = [[] for _ in range(N+1)] # 주어지는 그래프 정보 담는 N개 길이의 리스트
distance = [INF] * (N+1) # 비용계산용 테이블
start = int(input()) # 최단거리의 기준
for _ in range(M):
a, b, cost = map(int, input().split())
graph[a].append((b, cost)) # 양방향 그래프로 안해주면 버그터짐 ㅋㅋ
graph[b].append((a, cost)) # 무족권 양방향으로 해주삼
def dijkstra(start):
queue = []
heapq.heappush(queue, (0, start)) # 시작할 때 (0, 본인 번호로 시작점을 잡고요)
distance[start] = 0 # 배열 초기화 해주시고
while queue:
dist, now = heapq.heappop(queue) # 비용, 본인 번호 이런식으로 뽑은 다음
if distance[now] < dist: # 새로 뽑은 비용이 원래 비용보다 더 비싸면 걸러줌
continue
for i in graph[now]: # 그리고 만약 새로 뽑은 비용이 더 저렴하다?
cost = dist + i[1] # 바로 비용계산 (여기까지 오기위해 쓴 비용 + 여기서 그 다음노드로 갈때 쓸 비용)
if cost < distance[i[0]]: # 이거 계산해서 만약 distance 테이블에 원래 있는 비용보다 더 싸면
distance[i[0]] = cost # 바로 초기화
heapq.heappush(queue, (cost, i[0]))
dijkstra(start)
for i in range(1, N+1):
if distance[i] == INF: # INF는 초기할당을 해준 값이구요 간선이 없어서 방문을 못했으면 최소비용도 못구해서 INF로 남아잇음
print("INF")
else:
print(distance[i])
# PROBLEM - 녹색 옷 입은 애가 젤다지?
# TIER - G4
# NUMBER - 4485
# DATE - 2022-08-11 19:07
# IDEA - 데이크스트라 기본이지만 2차원배열을 사용해서 BFS같이 푸는게 특징
import sys
import heapq
input = sys.stdin.readline
def dijkstra(count, sx, sy, N): # N = 그래프의 크기
queue = []
heapq.heappush(queue, (graph[sx][sy], sx, sy))
distance[sx][sy] = 0
while queue:
cost, x, y = heapq.heappop(queue)
if x == N-1 and y == N-1: # 만약 뽑아낸 x, y가 목적지일 경우
print(f'Problem {count}: {distance[x][y]}') # 비용 출력하고 종료
break
for i in range(4): # 4방향 탐색
nx, ny = x+dx[i], y+dy[i]
if 0 <= nx < N and 0 <= ny < N:
new_cost = cost + graph[nx][ny] # 새로운 금액(현재까지 온 비용 cost + 다음으로 갈 위치의 비용)이
if new_cost < distance[nx][ny]: # 원래 그 자리에 있던 비용보다 작을 경우 -> 업데이트
distance[nx][ny] = new_cost
heapq.heappush(queue, (new_cost, nx, ny)) # 그리고 새로 업데이트한 자리를 heap에 넣어서 그다음 탐색 ㄱ
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
count = 1
INF = int(10e9)
while (N := int(input())) != 0:
graph = [list(map(int, input().split())) for _ in range(N)]
distance = [[INF] * N for _ in range(N)]
dijkstra(count, 0, 0, N)
count += 1
