17 Jul 2020

[BOJ 9372]

상근이의 여행

문제 바로가기 : https://www.acmicpc.net/problem/9372

Solution 1


MST(Minimum spanning tree) 알고리즘으로 풀 수 있다고 해서 찾아보니깐 생각보다 어렵지 않았다.
그런데 문제를 잘 읽어보니 도시별로 가중치(거리)의 차이가 없었다. 그래서 실버3인가?
읽었던 내용을 토대로 쓰다보니 코드가 좀 길어졌다.
종료조건을 어떻게 할까 시행착오를 겪다가 어차피 도시는 n개고 비행기 1대는 2개의 도시를 다니니까
최종적으로 n-1이 됐을 때 나오면 되지 않을까 싶어 종료 조건으로 설정했다.
? 무조건 답은 나올테니까 도시를 다 지나는 input이 들어올텐데? ㅋㅋ??

solution 2


맞다. 다른거 다 필요없고 답은 n-1이었다.
겁나 허무하다.

Location

Icheon, KR

Email

iteratively@naver.com

Social

-->