백준 1976번 문제(여행 가자) 파이썬(Python) 풀이 [로밍맨]

문제 링크

www.acmicpc.net/problem/1976

1976번: 여행 가자

 

정답 코드는 아래와 같습니다.

def find(i, rst):
  if rst[i] != i:
    rst[i] = find(rst[i], rst)
  return rst[i]
 
def union(i, j, rst):
  x = find(i, rst)
  y = find(j, rst)
  rst[x] = y
 
def solve():
  n = int(input())
  m = int(input())
  arr = []
  for _ in range(n):
    tmp = [int(x) for x in input().split()]
    arr.append(tmp)
  test = [int(x) - 1 for x in input().split()]
  rst = list(range(n))
  for i in range(n):
    for j in range(i+1, n):
      if arr[i][j] == 1:
        union(i, j, rst)
  pivot = find(test[0], rst)
  for i in range(1, m):
    if pivot != find(test[i], rst):
      print("NO")
      return
  print("YES")
 
solve()
 

 

본 풀이는 union-find 를 안다는 전제하에 설명됩니다.

 

728x90

 

이 문제는 그래프의 임의의 두 노드가 서로 연결 가능한지를 묻고 있습니다.

traverse 알고리즘을 이용하여 탐색해 나가는 것도 하나의 방법이라고 할 수 있겠지만,

생각을 조금 바꾸어서 서로 연결되어 있는 노드들끼리 하나의 집합을 이룬다고 가정합니다.

이렇게 되면 아래 두 문장이 동일한 문장이 됩니다.

1. 두 노드가 서로 연결 가능한가?

2. 두 노드가 같은 집합에 속해 있는가?

따라서 각 query 에 대하여 두 노드가 서로 같은 집합에 속해있는지를 확인해주면 됩니다.

 

풀이는 아래 영상 참고 바랍니다.

www.youtube.com/watch?v=g2Wc-4IemMk

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)