[문제풀이] 백준 1976번 여행가자

 

 

문제

---

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

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 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라는 여행경로를 통해 목적을 달성할 수 있다.

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

 

 

 

 

문제풀이

---

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

# 도시의 수 입력
n = int(input())

# 여행계획에 속한 도시들의 수
m = int(input())

# 도시의 수에 대한 연결 정보
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
plan = list(map(int, input().split()))

# 부모 테이블 생성 및 초기화
parent = [0]*(n+1)
for i in range(1, n+1):
    parent[i] = i

# 서로소 집합 만들기
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            union_parent(parent, i+1, j+1)

check = True
# 여행 계획에 있는 노드의 루트가 동일한지(같은 집합에 있는지)
for i in range(m-1):
    if find_parent(parent, plan[i]) !=  find_parent(parent, plan[i+1]):
        check = False
if check:
    print('YES')
else:
    print('NO')