여행 가자 ( 1976 번 )

1976번: 여행 가자

 

---

🧠 알고리즘

• 유니온 파인드 (Union-Find, Disjoint Set Union)

 

✔️ 동작 방식

문제 핵심 아이디어

• 그래프에서 여러 도시 간 연결 여부를 확인하는 문제로,
  "모든 도시가 하나의 연결된 네트워크(같은 집합)에 속해 있는가?"를 판단한다.
• 유니온 파인드(Union-Find) 자료구조를 이용해 효율적으로 집합 병합(Union) 및 대표 노드 탐색(Find) 을 수행한다.

세부 동작 구조

1. 초기화
   • pt_list[i] = i 로 자기 자신이 부모인 독립 집합으로 초기화.
2. Union 과정
   • 인접 행렬을 순회하며 1(연결됨)이면 두 도시를 Union 연산으로 하나의 집합으로 합침.
   • _find() 함수를 통해 각 도시의 루트 노드를 찾아 병합.
   • 더 작은 루트 번호를 부모로 하여 병합함으로써 트리 균형을 어느 정도 유지.
3. Find 과정 (경로 압축 포함)
   • _find()는 루트 노드를 찾을 때 경로 압축(Path Compression) 을 수행하여
     다음 탐색 시 O(1)에 가깝게 루트를 찾도록 함.
4. Checking 과정
   • 여행 계획에 포함된 모든 도시가 같은 루트(parent) 를 가지는지 확인.
   • 하나라도 다르면 False, 모두 같으면 True → "YES" 출력.

---

 

🧾 코드

import sys

def _checking(path):
    answer = _find(path[0])
    for visit in path:
        now_root = _find(visit)
        if pt_list[now_root] != answer:
            return False
    return True


def _find(num):
    while pt_list[num] != num:
        pt_list[num] = pt_list[pt_list[num]]
        num = pt_list[num]
    
    return pt_list[num]


def _union(x, y):
    x_root, y_root = _find(x), _find(y)
    if x_root > y_root:
        pt_list[x_root] = y_root
    else:
        pt_list[y_root] = x_root
        

def _main(n, m):
    for i in range(1, n + 1):
        conn_list = list(map(int, sys.stdin.readline().rstrip().split()))
        
        for idx in range(i, n):
            if conn_list[idx] == 1: # 연결
                a1_root, a2_root = _find(i), _find(idx + 1)
                _union(a1_root, a2_root)

    path = tuple(map(int, sys.stdin.readline().rstrip().split()))

    if _checking(path):
        return "YES"
    return "NO"

    
n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
pt_list = [i for i in range(n + 1)]
print(_main(n, m))

---

 

⏱️ 시간 복잡도

for i in range(1, n + 1) : 도시 순회 ( 선형 시간 복잡도 )
	for idx in range(i, n) : 현재 도시와 연결 도시 체킹 ( 선형 시간 복잡도 )
    	# 유니온 파인드 - 경로 압축 ( 상수 시간 )
        _find(num)
        _union(x, y)
        
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )