joseph0528 코딩 블로그

solved.ac 티어 : 골드 3 https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제의 풀이는 생각보다 간단하다. 1에서부터 시작해서 dfs으로 끝점(괴도 루팡이 있다는 곳)까지 탐색하면서 지나온 길의 가중 치중 가장 작은 값을 찾고 모아지는 부분에서 더해주면 된다. 문제에 있는 예시로 설명을 해보겠다 괴도 루팡이 있을 수 있는 곳은 3,4,6,7번 점이다. 1부터 3,4,6,7인곳으로 dfs으로 탐색하면 된다. 일단 3부터 시작하..