여행 계획

출처::  

분류:: 서로소 집합 알고리즘

 

1. 문제 이해 및 해결과정

- 서로소 집합 알고리즘을 이용하여, 그래프에서 노드 간의 연결성을 파악하여 해결해야한다. - 서로소 집합 알고리즘을 이용하는 이유: 여행계획에 해당하는 모든 노드가 같은 집합에 속하면 가능한 여행결로 - 두 노드 사이에 도로가 존재하면 -> union 연산 - 여행계획에 포함되는 모든 노드가 모두 같은 집합에 속하는지 체크하면 정답

2. 풀이방법

 1. UNION-FIND 서로소 집합 알고리즘

#여행 계획
#
import sys
sys.stdin = open("input.txt","r")
n,m=list(map(int,input().split()))
parent = [0]*(n+1) #부모 테이블 초기화

#부모 테이블 상에서, 부모를 자기 자신으로 초기화
for i in range(1,n+1):
    parent[i]=i

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

#union연산 각 수행
for i in range(n):
    data=list(map(int,input().split()))
    for j in range(n):
        if data[j]==1: #연결되어있으면 union연산 실행
            union_parent(parent,i+1,j+1)
#여행 계획
plan=list(map(int,input().split()))

result=True
for i in range(m-1):
    #여행계획에 속하는 노드의 루트노드가 같은지 확인
    if find_parent(parent,plan[i])!=find_parent(parent,plan[i+1]):
        result=False

#여행 계획에 속하는 모든 노드가 서로 연결되어있는지 확인
if result:
    print("YES")
else:
    print("NO")

 

3. 오답원인

 

4. 알게된 점