2019 CAL Season 1 #D 풀이

문제 원본 : https://www.acmicpc.net/problem/1976

1976번: 여행 가자

출제자 : 31기 김건형

 

맞은 동아리

: 로고스 / EXE&GAIA

정답 소스코드

풀이법은 다음과 같습니다.

Union-Find 알고리즘을 사용하여 도시와 도시 사이 연결정보를 저장합니다.

모든 길에 대한 입력을 받고 연결 정보를 배열에 저장합니다. (본문에서 int형 배열 root)

연결되었다는 정보가 주어졌을 때 연결된 묶음 중 최상위 도시와 연결되었다고 표시함으로써 구현할 수 있습니다.

위와 같은 과정을 반복하여 연결 정보를 모두 저장한 후 여행 계획으로 주어지는 도시들의 root를 비교합니다.

만약 여행계획에 있는 임의의 두 도시에 대하여 가리키는 root가 서로 다르다면 여행 계획은 성립할 수 없습니다.

위와 같은 방법으로 원하는 정답을 얻을 수 있습니다.