BOJ - 1976

백준 문제 링크
여행 가자

❓접근법

1. 서로소 집합 알고리즘을 사용했다.
   -> 각 원소가 속한 집합을 알 수 있다.
2. 특정 원소가 속한 집합을 찾는 함수 find_parent,
   두 원소가 속한 집합을 합치는 함수 union_parent 2개가 필요하다.
3. 자기 자신으로 초기화한 부모 테이블 parent를 만들고,
   도시의 연결 정보에서 1 이라면 두 원소를 union_parent 한다.
4. plans를 받아주고, 중복을 제거한 plans_set을 만들어준다.
   plans의 첫번째 원소가 속한 집합을 찾을 변수 check를 만든다.

check = find_parent(parent, plans[0]) # 여행 계획의 첫번째 원소가 속한 집합을 찾기

5. 이제 plans_set을 돌면서, 다른 원소들이 첫번째 원소의 집합과 다르다면
   'NO'를 출력 후 프로그램을 종료하고, 같으면 'YES'를 출력한다.

for i in plans_set:
    if find_parent(parent, i) != check: # 여행 계획의 원소가 속한 집합이 첫번째 원소가 속한 집합과 다르면 NO를 출력
        print('NO')
        exit(0)
print('YES')

👌🏻코드

def find_parent(parent, x):
    if parent[x] != x:
        return 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
        
n = int(input())
m = int(input())

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

for i in range(n):
    x = list(map(int, input().split()))
    for j in range(n):
        if x[j] == 1:
            union_parent(parent, i + 1, j + 1)
            
plans = list(map(int, input().split()))
plans_set = set(plans)

check = find_parent(parent, plans[0]) # 여행 계획의 첫번째 원소가 속한 집합을 찾기

for i in plans_set:
    if find_parent(parent, i) != check: # 여행 계획의 원소가 속한 집합이 첫번째 원소가 속한 집합과 다르면 NO를 출력
        print('NO')
        exit(0)
        
print('YES')