[알고리즘] 백준 1976(파이썬)

일반적으로 코테에 많이 나올 수 있는 유형이라고 생각한다. 간선들의 정보를 주어주었을 때 임의의 두 정점이 연결이 되었는지 묻는 문제이다.

이 문제의 해결 방법에는 다양한 방법이 있겠지만 크게 두 경우를 살펴볼 수 있다.
바로 플로이드-워셜을 이용하는 것과 유니온-파인드를 이용하는 것이다.

첫 번째로 플로이드-워셜을 이용하는 풀이는 간선의 정보를 토대로 가중치를 임의의 값(ex 1)로 두어 각 정점에서 다른 정점으로의 최단거리를 구하는 것이다. 이 때 최단거리가 구해지면 갈 수 있고 구해지지 않고 INF로 남아있으면 갈 수 없다.

두 번째로 유니온-파인드를 이용하는 풀이는 간선의 정보를 토대로 두 정점을 FIND시켜 조상의 값을 하나의 리스트에 넣는 것이다. 이렇게 되면 같은 조상에 있는 노드들은 만날 수 있고 다른 조상에 있는 노드들은 만날 수 없게 된다.

플로이드 워셜은 시간복잡도가 O(n^3)이며 유니온-파인드는 거의 상수배에 가능하기 때문에 유니온-파인드를 사용하는 것이 유용한 문제라고 볼 수 있다. 또한 메모리적으로도 플로이드-워셜은 모든 간선들의 정보를 표현해야 하지만 유니온-파인드는 조상의 노드만 표현하기 때문에 유리하다. 따라서 유니온-파인드를 사용하여 문제를 풀었다.

import sys

n = int(input())
total = int(input())

def find(k):
    if check[k] != k:
        check[k] = find(check[k])

    return check[k]


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

for i in range(n):
    tar = list(map(int, sys.stdin.readline().split()))

    for j in range(len(tar)):
        if tar[j] == 1:

            first = i + 1
            second = j + 1

            f = find(first)
            s = find(second)

            if f < s:
                check[s] = f
            else:
                check[f] = s

# print(check)

end = list(map(int, sys.stdin.readline().split()))

err = 0
for i in range(total-1):
    if find(end[i]) != find(end[i+1]):
        err += 1
        break

if err == 0:
    print("YES")
else:
    print("NO")