https://www.acmicpc.net/problem/9372필요한 로직 : 없음입력만 정상적으로 받고 N-1만 출력하면 끝나는 당황스러운 문제다. 이 문제는 최소 스패닝 트리를 묻는 문제가 아니기 때문이다. 그래프를 구성하는 스패닝 트리는 아래 예시처럼 다양하게 있을 수 있다. 그 중 가장 적은 비용으로 스패닝 트리를 구성하는 알고리즘이 bfs, 크루스칼, 프림 알고리즘인데 이 문제의 경우 가중치가 모두 같고 연결 그래프 내에서 정점을 여러번 방문해도 되며 단순히 모든 정점을 순회할 수 있는 간선수만 출력하면 된다. 그렇다면 정점 V개를 이을 V-1개의 간선을 출력하면 끝난다. 필요한 로직 "없음"!가중치 1로 두고 굳이 bfs를 쓰고 싶..........
9372번 상근이의 여행에 대한 요약내용입니다.
자세한 내용은 아래에 원문링크를 확인해주시기 바랍니다.
원문링크 : 9372번 상근이의 여행
네이버 블로그
티스토리
커뮤니티