다익스트라4 [백준 10282번] 해킹 문제 풀이 '이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다' 라는 문구에서 방향이 있는 그래프임을 알 수 있다. 테스트 케이스의 크기만큼 반복하여, 다익스트라 알고리즘을 이용해 개수와 최대값을 구하면 감염된 컴퓨터의 개수와 모두 감염되는데 걸리는 시간을 구할 수 있다. import sys import heapq input = sys.stdin.readline INF = int(1e9) test_num = int(input()) def dijkstra(start): q = [] distance = [INF] * (n + 1) heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, no.. 2023. 8. 9. [백준 1238번] 파티 문제 풀이 먼저 간단한 다익스트라 구조를 이용하여 가는 거리와 오는 거리를 구해 최댓값을 구했는데, 입출력은 동일하나 시간 초과가 나왔다. 그래서, 힙을 이용하여 개선된 다익스트라 알고리즘을 사용하였더니 해결되었다. import sys import heapq input = sys.stdin.readline INF = int(1e9) # 노드의 개수, 간선의 개수 입력 받기 n, m, x = map(int, input().split()) # 각 노드에 연결 되어 있는 노드에 대한 정보를 담는 리스트 만들기 graph = [[] for i in range(n +1)] # 모든 간선 정보를 입력 받기 for _ in range(m): a, b, c = map(int ,input().split()) # a번 노드에서 b번.. 2023. 8. 8. [개념] 다익스트라 알고리즘 간단한 다익스트라 알고리즘은 O(V^2)의 시간 복잡도를 가진다. ( V는 노드의 개수 ) ✔ 방법 1 import sys input = sys.stdin.readline INF = int(1e9) # 노드의 개수, 간선의 개수 입력 받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력 받기 start = int(input()) # 각 노드에 연결 되어 있는 노드에 대한 정보를 담는 리스트 만들기 graph = [[] for i in range(n+1)] # 방문한 적이 있는지 체크하는 목적의 리스트 만들기 visited = [False] * (n+1) # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) # 모든 간선 정보를 입력.. 2023. 8. 3. [개념] 최단 경로 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘으로, '길 찾기' 문제라고도 불린다. 최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3가지 이다. 이 중, 다익스트라 최단 경로와 플로이드 워셜 알고리즘이 가장 많이 등장한다. 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 적용된다. 1. 다익스트라 최단 경로 알고리즘 : 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 .. 2023. 7. 26. 이전 1 다음
