[백준] 여행 가자

출처::  www.acmicpc.net/problem/1976

분류:: 유니온파인드 

 

1. 문제 이해 및 해결과정

- 1,2,3이 같은 집합인지 확인하기

 

2. 풀이방법

  1. 유니온파인드 [python]

#여행 가자
#https://www.acmicpc.net/problem/1976
import sys
sys.stdin = open("input.txt","r")
n=int(input()) #도시 수
m=int(input()) #여행계획에 속한 도시 수
board=[list(map(int,input().split())) for _ in range(n)]
plan=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

for i in range(n):
    for j in range(n):
        if board[i][j]==1: #연결되어 있으면
            union_parent(parent,i+1,j+1) #합침(인덱스조심)
for i in range(m-1):
    #부모 다르면, 같은 집합 아님
    if find_parent(parent,plan[i])!=find_parent(parent,plan[i+1]):
        print("NO")
        break
else:
    print("YES")

 

3. 오답원인

 

4. 알게된 점