[알고리즘] 백준1976 여행가자 - 파이썬

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

1976번: 여행 가자

 

 

[풀이 코드]

from sys import stdin

input = stdin.readline

n = int(input())
m = int(input())

parent = [i for i in range(n+1)]

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for i in range(1, n+1):
    graph = list(map(int, input().split()))

    for index, value in enumerate(graph):
        if value == 1:
            union_parent(parent, i, index + 1)


tour = list(map(int, input().split()))
result = set([find_parent(parent, i) for i in tour])

if len(result) != 1:
    print("NO")
else:
    print("YES")

- 기본적인 유니온 파인드 문제이다. union_parent 함수와 find_parent함수는 그대로 활용했다.

 

- 입력 마지막 줄에 여행 계획이 주어지고 이를 하나씩 확인하는 법을 다른 분의 코드를 보았다.. 계속 indexerror가 나서 이 부분인 줄 알고 참고한 건데 알고 보니 parent배열을 선언할 때 났었던 에러.. 어찌 됐든 set을 활용하는 방법이 내가 작성했던 코드보다 더 깔끔한 것 같다.