BOJ 백준/그래프, 경로 검색 결과

해당 글 3건

백준 02623 - 음악프로그램

출처 : https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 고려 사항 위상 정렬 알고리즘! 주어진 정보를 활용하여, vector[가수 번호] = { 연결된 노드 리스트 ( 연결 당한 노드들 ) }, array[가수 번호] = 연결 당한 횟수. 연결 당한 횟수가 0 인 가수 번호를 큐에 삽입. 큐가 비지 않으면 반복해서, 1. 정답 벡터에 제일 먼저 들어온 가수를 담고 pop 한다. 2. 그 가수가 연결한 가수 번호들의 cnt ..
BOJ 백준/그래프, 경로 2021. 4. 6. 21:13

백준 01647 - 도시 분할 계획

출처 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 고려사항 최소 신장 트리 문제! 도시를 두 개로 분할했을 때의 최소 도로 비용은 최소 신장 트리로 모든 도시를 연결했을 때, 가장 비싼 비용의 도로를 제거해주면 2개로 나뉜다! 프림 방식으로 풀었다. 프림 방식은 1. 노드(vertex)를 선택 하고, 그 노드에 연결된 edge들을 minHeap 에 담아준다. 2. 힙에서 e를 꺼내고, 해당 e를 통해..
BOJ 백준/그래프, 경로 2021. 4. 6. 20:11

백준 01504 - 특정한 최단 경로

출처 : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 고려사항 - 다익스트라 알고리즘 사용 - INF 는 800개의 정점이 직선으로 쭉 연결되었을 때의 최대값인 800 * 200000 + 1 - s -> v1 -> v2 -> e 인 경우와 s -> v2 -> v1 -> e 인 경우를 모두 구해서 작은 값 리턴, 마지막으로 65 - 81 줄과 같이 경로인지 판별해야함. 아닐시 -1 출력 깨달은 점 ..
BOJ 백준/그래프, 경로 2020. 10. 24. 03:28