악곱 == 악성곱슬

유니온 파인드

---

본 문제도 그래프 자료구조를 이용하여 문제를 해결해야 하는 문제이다.

본 문제에서 도시간의 연결 여부를 판단하는 부분에서 유니온 파인드 알고리즘을 사용하여 탐색을 할 수 있음을 알 수 있다. 그래프를 순회하며 연결 정보를 확인하며 1이면 union연산을 수행하여 집합을 묶는다. 이후 주어진 두 정점에 대해 find연산으로 판별한다.

이 문제는 모든 도시간의 간선의 비용이 1이므로 탐색에 있어서 DFS, BFS를 이용하여 어거지로 구현할 수도 있다. 하지만 복잡하니 유니온 파인드 유형을 항상 염두하며 풀자.

import sys

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

def solution(n, m):
    parent = [0] * (n + 1)
    for i in range(n + 1):
        parent[i] = i
    graph = list()
    for _ in range(n):
        graph.append(list(map(int, sys.stdin.readline().rstrip().split())))
    plan = list(map(int, sys.stdin.readline().rstrip().split()))
    for i in range(n):
        for j in range(i, n):
            if graph[i][j] == 1:
                union_parent(parent, i+1, j+1)
    answer = True
    for i in range(1, m):
        if find_parent(parent, plan[i - 1]) != find_parent(parent, plan[i]):
            answer = False
            break

    return answer

if __name__ == "__main__":
    sys.setrecursionlimit(100000)
    N = int(sys.stdin.readline().rstrip())
    M = int(sys.stdin.readline().rstrip())
    if solution(N, M) is True:
        print("YES")
    else:
        print("NO")