[백준] 1976번 여행 가자(python)

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

1976번: 여행 가자

 

1. 난이도 골드4 (🥇)

 

2. 문제 해결 방법

단계별로 풀어보기 중 union find로 분류되어 있어서 바로 풀었다. 

 

무방향 그래프에서 cycle을 찾기 위해서는 union find를 이용하면 쉽다는 것을 잊지말자

 

 

3. 내가 작성한 코드

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input().rstrip()) #도시의 수
m = int(input().rstrip()) #여행 계획에 속한 도시의 수

parent = [0] * (n+1)

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

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

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

town = [] #각 도시끼리 연결되어 있으면 union 연산 
for i in range(n):
  town.append(list(map(int, input().rstrip().split())))

for i in range(n):
  for j in range(n):
    if town[i][j] == 1:
      union(i+1,j+1)

travel = list(map(int, input().rstrip().split()))

x = parent[travel[0]]
check = 0

for i in travel: #travel 도시의 root node가 모두 같으면 cycle이 있는 것 
  if x != parent[i]:
    check += 1
    break

if check == 0:
  print("YES")
else:
  print("NO")

 

4. 메모

union find 문제라는 걸 알고 있지 않았으면 플로이드 워셜로 풀었을 것 같다. M이 1000이라 시간복잡도에서 오류가 났겠구나

 

알고리즘 유형별로 좀 더 다듬은 후에, 문제와 데이터 크기를 보고 올바른 알고리즘을 떠올리는 방법을 훈련하도록 해야겠다.

 

(setrecursionlimit 갱신을 안해줘서 계속 틀렸었다 ㅋㅋ ㅜㅜ)