[백준]1976 여행가자(Python)

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

1976번: 여행 가자

 

문제 접근

 

입력한 값들을 분리해서 도시끼리 연결하는 과정도 빡셌는데.. 그 이후의 코드를 어떻게 구현할지 막막

 

코드

import sys

sys.setrecursionlimit(1000000)  # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

# 찾기 연산(같은 집합에 속하는지 확인)
def find_parent(x):
    if parents[x] != x:
        parents[x] = find_parent(parents[x])
    return parents[x]


# 합집합 연산(두 집합을 합치기 위한 함수)
def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

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

parents = [i for i in range(N+1)]

for i in range(N):
    con = list(map(int, input().split()))
    for j in range(N):
        if con[j] == 1:
            union_parent(i+1, j+1)  # i번 도시와 j번 도시 연결

# 경로 체크
travel = list(map(int, input().split()))
start = parents[travel[0]]  # 출발 도시의 루트 노드를 저장 
for i in range(1, M):   # 여행 계획에 포함된 도시들을 두 번쨰 도시부터 마지막 도시까지 순회 
    if find_parent(travel[i]) != start: # 현재 도시의 루트 노드가 출발 도시의 루트 노드와 다르다면
        print("NO") # 도시들 연결x
        break
else:
    print("YES")

 

문제 회고

 

생각해 보니까 괜히 어떤 식으로 경로가 이어지는지 출력하는 것 때문에 겁먹은 것 같다.
그저 여행 계획에 포함된 도시들 중에 하나라도 루트 노드가 다르다면 이는 여행이 불가능하다는 것만 제대로 파악하면 쉽게 코드를 작성할 수 있다.