Coding Test/Graph

[1753번] 최단경로 구하기 (다익스트라, 우선순위큐, 힙)

다익스트라 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 기출 : 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택 노드를 돌아가면서, 더 거리가 나오면 값 갱신하여 저장 우선순위 큐 파이썬 우선순위 큐, 힙 우선순위 큐(Priority Queue) 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나 karla.tistory.com 풀이 (PriorityQueue) import sys from queue import Priori..

[1516번] 게임 개발하기 (위상정렬)

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 항상 유일한 값으로 정렬되지 않음 ex) 롤 아이템, 수강신청 풀이 from collections import deque """ 위상정렬 : 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 모든 건물을 짓는데 걸리는 최소 시간 여러 개의 건물을 동시에 지을 수 있음 N개의 건물을 지을 때 각 건물을 짓기 위해 필요한 최소 시간 출력 건물의 종류 수 n(1~500) 각 건물을 짓..

[1717번] 집합의 표현 (유니온 파인드)

1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 유니온 파인드 여러 노드가 있을 때, 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되어 있는 알고리즘 union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산 find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 원리 1차원 리스트 이용, 각 노드가 모두 대표 노드이므로 리스트는 자신의 인덱스 값으로 초기..