[백준] 1976. 여행 가자/Python - Gold4

❓문제

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

성능 요약

메모리: 32412 KB, 시간: 40 ms

분류

그래프 이론, 자료 구조, 그래프 탐색, 분리 집합

 

문제 설명

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

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

✍🏻풀이

첫 번째 줄에 도시 수와 두 번째 줄에 여행 계획에 속한 도시 수가 주어진 후 N개의 줄에 N 개의 정수가 주어진다. 여기서 i행 j열은 i 번 도시와 j 번 도시의 연결 정보를 나타낸다. 그러므로 입력을 받아서 바로 union을 만들어 집합 정보를 기록한다.

그 다음 여행 계획을 받아서 현재 도시와 다음 도시가 서로 연결되어있는지 확인한다. 그리고 연결되어있지 않다면 "NO"를 출력한 후 멈추고 for문을 중간에 멈추지 않고 끝냈다면 else에 의해서 "YES"를 출력한다.

💻코드

import sys

input = sys.stdin.readline

N = int(input()) # 도시 수
M = int(input()) # 여행 계획에 속한 도시 수
parent = [i for i in range(N)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])

    return parent[x]

def union(a, b):
    a, b = find(a), find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a

for i in range(N):
    status = list(map(int, input().split()))
    for j in range(N):
        if status[j]:
            union(i, j)

plan = list(map(int, input().split())) # 여행 계획

for i in range(M-1):
    if parent[plan[i]-1] != parent[plan[i+1]-1]:
        print("NO")
        break
else:
    print("YES")

📍후기

처음에 입력 방식을 보고 바로 이해되지 않아서 오래 걸렸다... 그리고 코드 순서 바꾸면서 몇 개 빠뜨리고 바꿨더니 에러도 났다...ㅎㅎ