🥚문제

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

• 그래프 이론
• 그래프 탐색
• 트리
• 깊이 우선 탐색

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline


def find(i):
    # 노드 i의 부모를 찾는다
    if parents[i] == i:
        return i
    parents[i] = find(parents[i])
    return parents[i]


def union_find(i, j):
    # 연결되어 있는 노드i - 노드j 유니온파인드
    i = find(i)
    j = find(j)
    if i < j:
        parents[j] = i
    elif i > j:
        parents[i] = j
    else:
        return


N = int(input().strip())
M = int(input().strip())
graph = [[0]*(N+1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
plan = list(map(int, input().split()))

# union-find, disjoint-set
parents = [0] + [x for x in range(1, N+1)]  # 부모 노드 번호 저장
for i in range(1, N+1):
    for j in range(1, N+1):
        if graph[i][j] == 1:
            union_find(i, j)

# union-find 이후 plan에 속한 도시들을 x라고 하면
# parents[x]가 모두 같은 값이면 여행이 가능하다
ans = "YES"
for i in range(len(plan) - 1):
    if parents[plan[i]] != parents[plan[i+1]]:
        ans = "NO"
        break
print(ans)

---

🧂아이디어

그래프 이론: union-find ✨

• union find 기법을 이용한다.

  1. parents라는 리스트를 만들어 parents[i] = i의 부모 노드 번호를 저장한다. 초기값은 parents[i] = i로 할당한다.

  2. 인접행렬 graph를 순회하며 i, j가 연결되어 있다면 i, j에 대해 union_find를 실시한다.

  3. union_find 함수 내부에서는 노드 i와 노드 j의 부모노드를 각각 찾는다. 이후 더 작은 값을 갖는 부모노드의 값으로 union한다.

  4. 모든 연결된 i, j에 대해 union_find를 마치면, parents 리스트 내에서 서로 연결된 노드들은 같은 부모값을 갖게된다.

• 노드들이 같은 집합 내에 있다면 서로 연결되어 있음을 의미한다.

• 따라서 "YES"를 출력하기 위해서는 여행 계획으로 입력 받은 도시 번호들이 union-find한 결과 모두 같은 집합 내에 속해야 한다. (parents[x]의 값이 모두 같아야 한다.)