백준(baekjoon) 1976번: 여행 가자(골드 4, 파이썬 PYTHON) - 유니온 파인드

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

 

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

 

import sys

N=int(sys.stdin.readline())
M=int(sys.stdin.readline())
parent=[None for _ in range(N+1)]

for x in range(1,N+1):
  parent[x]=x

def find(city):
  if(parent[city]==city):
    return city
  a=find(parent[city])
  parent[city]=a
  return a

def union(city1,city2):
  a=find(city1)
  b=find(city2)
  if(a==b):
    return
  if(a<b):
    parent[b]=a
  else:
    parent[a]=b

for x in range(1,N+1):
  link=list(map(int,sys.stdin.readline().split()))
  for y in range(1,N+1):
    if(link[y-1]==1):
      union(x,y)

flag=True
travel=list(map(int,sys.stdin.readline().split()))
travel.sort()

for x in travel:
  if(parent[x]!=travel[0]):
    flag=False
    break

if(flag==True):
  print("YES")
else:
  print("NO")

 

※ 유니온 파인드

 

 

● 만약 두 도시가 연결되어 있으면 더 번호를 가지고 있는 도시의 부모를 더 작은 번호를 가지고 있는 도시의 번호로 설정해 준다는 것이 기본 전제이다. 우선 모든 도시의 부모를 자기 자신의 번호로 설정해 놓는다.

 

● 두 도시가 연결되어 있다는 정보가 들어오면 두 도시의 번호를 union 함수의 매개변수로 전달해준다. 만약 두 도시의 부모가 같다면 이미 합해져 있는 것이므로 그대로 return 해준다. 만약 한 쪽 도시의 부모가 더 크다면 번호가 더 큰 도시의 부모를 더 작은 번호의 도시로 설정해준다. 그러면 두 도시의 부모는 같게 되고, 이는 두 도시가 서로 연결되어 있음을 나타낸다.

 

● union 함수 안에 들어온 번호의 도시가 현재 가리키고 있는 부모를 찾기 위해 find 함수를 호출할 때, 도시의 부모가 이 도시가 속해있는 도시의 집합에서 가장 작은 번호를 가지고 있는 도시를 가리키고 있지 않을 수도 있으므로 부모가 자기 자신인 도시가 나올 때 까지 재귀적으로 함수를 호출해 주어야 한다. 

 

● 위 과정이 모두 끝나고 여행계획이 주어지면, 주어진 여행계획에 속해있는 모든 도시가 같은 부모를 가지고 있으면 모두 연결되어 있다는 것이므로 YES를 출력, 아니면 NO를 출력해준다.