백준 1976번: 여행 가자 (Python)

접근

유니언파인드 알고리즘을 이용하여 풀 수 있다. 알고리즘에 대해서는 이전 글에서 자세하게 설명하여 링크를 남기도록 한다.

유니언파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python)

백준 1717번: 집합의 표현 (Python)

연결된 도시들끼리 유니언을 이용하여 집합을 만들어주고, 주어진 여행경로들이 같은 루트 노드를 가지고 있는지를 체크해주면 된다.

코드

import sys


def find(x):
    if connect[x] < 0:
        return x
    p = find(connect[x])
    connect[x] = p
    return p


def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if connect[x] < connect[y]:
        connect[x] += connect[y]
        connect[y] = x
    else:
        connect[y] += connect[x]
        connect[x] = y


n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
connect = [-1 for i in range(n + 1)]
for i in range(n):
    k = list(map(int, sys.stdin.readline().split()))
    for j in range(len(k)):
        if k[j]:
            union(i + 1, j + 1)
p = list(map(int, sys.stdin.readline().split()))
q = find(p[0])
isPossible = True
for i in p:
    if q != find(i):
        isPossible = False
if isPossible:
    print('YES')
else:
    print('NO')

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!