BaekJoon 1976번 : 여행 가자 (python)

BaekJoon 1976번 : 여행 가자 (G4 36.931%)

여행 가자 문제

Union-Find 활용 문제이다.

• 각 도시마다 연결되어 있는 리스트를 입력 받고 만약 연결되어있는 표시 1로 되어있다면 해당 노드들을 union(i+1,j+1)을 통해 합쳐주는 과정을 진행한다.
• 입력받은 모든 도시들을 연결하였을 때 최종 여행하는 plan 리스트들을 모두 find를 통해 비교해가며 모두 root노드가 같은 값으로 되어있는지 체크해준다.

---

import sys
input = sys.stdin.readline

def find(x) :
    if root[x] != x:
        root[x] = find(root[x])
    return root[x]

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

    if rootX != rootY :
        if rank[rootX] > rank[rootY] :
            root[rootY] = rootX
        elif rank[rootX] < rank[rootY] :
            root[rootX] = rootY
        else :
            root[rootY] = rootX
            rank[rootX] += 1

N = int(input())
M = int(input())

root = list(range(N+1))
rank = [1]*(N+1)

for i in range(N) :
    city = list(map(int,input().split()))
    for j in range(N) :
        if city[j] == 1 :
            union(i+1,j+1)

count = 0
plan = list(map(int,input().split()))
for i in range(M-1) :
    if find(plan[i]) == find(plan[i+1]) :
        count += 1

if count + 1 == M :
    print('YES')
else :
    print('NO')

---