1976: 여행 가자

풀이 시간

• 1h 10m
• print("No")가 아니라 print("NO")로 출력을 해야했다..

구현 방식

• 여행 계획에 포함된 도시들이 모두 같은 집합에 속해있다면 가능한 여행계획이고, 그렇지 않다면 불가능한 여행계획이다

• 분리 집합 -> find-union을 이용해서 풀었다

• 도시의 graph의 모든 edge를 순회하면서 root 부모노드(find(x)의 결과)가 다르다면 그 둘을 union을 해주는 방식으로 parent 리스트를 완성시킨다
  -> plan이 가능한 여행계획이려면 완성된 parent 리스트에서, plan에 속한 도시들은 모두 같은 부모노드를 가져야한다

코드

import sys

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

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

N = int(sys.stdin.readline().strip())
M = int(sys.stdin.readline().strip())

parent = [i for i in range(N+1)]
for n in range(1, N+1):
    tmp = list(map(int, sys.stdin.readline().strip().split()))
    for i in range(1, N+1):
        if tmp[i-1] == 1:
            union(n, i)

plan = list(map(int, sys.stdin.readline().strip().split()))
flag = find(plan[0])
for p in plan[1:]:
    if find(p) != flag:
        print("NO"); exit()
print("YES")

결과

• https://www.acmicpc.net/board/view/123621
  단순 오타였다