[Python] BOJ(백준) 1976번 - 여행 가자

링크

https://www.acmicpc.net/problem/1976

난이도(solved.ac 참고)

골드4

풀이

input값으로 인접 행렬 형태가 들어갈 거라고는 생각도 안하고 있다가 시간을 좀 날렸다.

핵심은 27행~31행인데, i에 대한 for문을 진행할때마다 list input을 받아서 j에 대한 for문을 다시 돈 다음, j-1번째 인덱스의 값이 1인지 아닌지 여부를 판단하였다. 이게 1이라면, 예를들어 (1, 2) 좌표가 1이라면 도시 1과 도시 2는 연결이 되어있는 것이다. 따라서 union으로 이 두 개를 합집합 처리를 한다.

 

이제 이렇게 할 경우 1로 들어간 부분에 대해서는 전부 합집합 처리가 되어, 연결이 되어있는 상태가 되었다. 이제 최상위 부모 노드를 찾는 find_parent를 마지막 input값에 대해 실행한 뒤 그 값을 전부 result라는 배열에 넣고, 이 값이 전부 같다면 집합 자료형인 set 처리를 했을 때 길이가 1이 나오게 된다.

 

이 값이 전부 같다는 것은 즉 마지막 input 값으로 들어가는 여행의 경로에 해당하는 마을들끼리가 전부 연결이 되어있는 상태라는 것이다. 왜냐면 그래야지만 이 마을들의 루트 노드가 하나로 통일이 되기 때문이다. 

 

전부 같다는 것은, 중복을 허용하지 않는 집합 자료형으로 바꿨을 때 내부 요소의 길이가 1이 되어야 한다. 이게 맞다면 YES로, 아니라면 NO로 처리했다.

 

처음에 마지막으로 들어가는 input값이 세개인 것을 보고 마지막으로 들어가는 input이 전부 세개라고 생각해서 a, b, c를 input으로 받아왔다가 ValueError이 떴다; 좀 더 문제를 잘 읽어야 겠다고 생각했다.