그래프 (3) 썸네일형 리스트형 [백준] 1948 임계경로 문제링크 : www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 출발점 s에서 e까지의 경로 중 가장 긴 길로 이동한 거리와 그 경로의 개수를 출력하는 문제이다. 간선의 방향이 존재하는 그래프이다. 위상 정렬로 출발점 s에서 어떤 x까지의 최장거리를 갱신했다. 어려운 점은 그 경로의 수를 구하는 것인데, 도착점에서 시작해서 시작점까지 가는 경로를 탐색했다. 이 때, x-> y로의 경로를 이용해서 도착점까지 갔는지를 파악하기 위해 dis.. [해커랭크] Roads and Libraries [JAVA] 문제링크: www.hackerrank.com/challenges/torque-and-development/problem Roads and Libraries | HackerRank Help the ruler of HackerLand determine the cheapest way to give his citizens access to libraries. www.hackerrank.com 모든 노드들을 잇는 최소한의 간선 개수는 노드의 갯수 -1이다. 그래서 도로를 고쳐서 도서관을 공유하는 비용을 최소한 하려면 도로를 N-1개만 고치면 된다. (MST 구성) 고장난 도로를 탐색해서 노드가 몇개인지 파악하기 위해 dfs 탐색을 했다. 또, N-1개의 도로의 수리비용보다 모든 노드에 도서관을 설치하는 비용이 적.. [백준] 15681 트리와 쿼리 문제링크: www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 너무 많이 풀어본 유형이라 쉬웠다. 문제 설명이 아주 구체적이어서 그래프와 트리의 개념을 이해하기에 좋고, 그것을 실습 해보는 목적으로 풀기에 좋은 문제인 것 같다. import java.io.*; import java.util.*; public class Main { public static int N,R,Q; public static .. 이전 1 다음