boj 1976 여행가자(골드4)

문제

boj 1976 여행가자

union find 문제이다

그냥 이런 패턴대로 익혀두고 그대로 쓰면 될것같다
지금까지는 이런형식 문제는 set으로 내맘대로 풀었는데
이게 거의 정형화된 최적화 풀이인것 같아서 공부했다

익숙해져야겠다

풀이

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

parent = [i for i in range(n+1)]

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

  parent[x] = find(parent,parent[x])
  return parent[x]

def union(parent,a,b):
  a = find(parent,a)
  b = find(parent,b)

  if a == b: return
  elif a < b :
    parent[b] = a

  else:
    parent[a] = b

for i in range(1,n+1):
  temp = list(map(int,input().split()))
  for j in range(len(temp)):
    if temp[j] == 1:
      union(parent,i,j+1)

question = list(map(int,input().split()))
answer = [find(parent,i) for i in question]

if len(set(answer)) == 1:
  print("YES")

else :
  print("NO")

결과