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

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

링크

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

난이도(solved.ac 참고)

골드4

문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

출력

첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

예제 입력

3

3

0 1 0

1 0 1

0 1 0

1 2 3

예제 출력

YES

나의 코드

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이 떴다; 좀 더 문제를 잘 읽어야 겠다고 생각했다.

from http://steadily-worked.tistory.com/665 by ccl(A) rewrite - 2021-08-13 19:26:09