BOJ 1976 _ Union-Find _ 파이썬

에구마·2023년 2월 23일

Algorithm

목록 보기

8/17

📃 문제

백준 1976번 여행가자

알고리즘 - Union - Find

문제 내 예시

💡 풀이 과정

1) parent 배열 시도 🤯

각 도시 별 갈 수 있는 도시들 중 숫자가 가장 작은 도시를 parent에 저장하려고 하였음
-> 다음 계획인 도시가 당장 갈 수 있는 도시이지만 숫자가 크다면 parent로만 발견할 수 없음

2) Union - Find 🥳

Idea : 그래프 모양을 만들거나 무작정 부모를 저장하는게 아니라 집합을 만드는 것이다

로직
1 / 2 / 3 / 4 / 5로 시작
첫줄입력으로 1:2,4,5가 나왔으니 현재(1)와 갈 수 있는 도시번호(각 2, 4, 5)를 Union 하여
1 2 4 5 / 3을 만든다.
각 도시별로 가장 작은 값을 parent로 가져서 같은 집합 내에 있음을 구분한다.
둘째줄입력으로 2:1,3,4 에 대하여도 반복
단, 2의부모는 1이 됐으니 1은 패스, 3만 Union, 4의 부모도 이미 1이니 패스

> 전체 코드
import sys
sys.stdin.readline

n = int(input())
m = int(input())

# find()
# 자신 == 자신의 부모라면, 자기가 그 집합 내 가장 작은 원소임.
# 그렇지 않다면, 자신의 부모의 부모를 계속 따라가면서 자기가 속한 집합 내 가장 작은 원소를 부모로 저장.
def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])
    return parent[a]

# union()
# 두 원소의 부모를 각각 구하고 그 중 큰 값을 작은 값으로 갱신 (같은 집합이라면 집 합 내 가장 작은 원소를 부모로 모두 가지기 때문)
def union(a,b):
    sp, bp  = min(find(a),find(b)), max(find(a), find(b))
    parent[bp] = sp

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

for i in range(n):
    li = list(map(int,input().split()))
    for j in range(n):
        if li[j] ==1: #j지만 인덱스니깐 실제론 j+1번째 도시인 셈
            union(i+1,j+1)

plan = list(map(int,input().split()))
def canwego():
    start = parent[plan[0]]
    for p in plan:
        if parent[p]!=start:
            print("NO")
            return
    print("YES")

canwego()