[백준 20040번] 사이클 게임 (Python3)

여러가지로 힘들었고 배운점도 많았던 문제이다.

 

처음에는 엄청 간단한 문제라고 생각했다.

"같은 집합에 속하면 cycle, 아니면 집합을 묶어주면 되잖아?"

라고 생각해서 모든 n에 대해 set()를 생성하고 연결될때마다 합쳐주는 방식을 생각했다.

 

코드는 아래와 같다.

import sys
input = sys.stdin.readline

N,M = map(int,input().split())

setdict = {}
for i in range(N):
  setdict[i] = {i}

finish = False
result = 0
for t in range(1,M+1):
  x,y = map(int,input().split())
  if finish:
    continue
  if x in setdict[y]:
    finish = True
    result = t
  else:
    setdict[x].update(setdict[y])
    setdict[y] = setdict[x]

print(result)

그러나 이 방법은 잘 되지 않았는데, 이유는 x의 set와 y의 set를 합치는 과정에서 x는 update가 되었지만 y는 update가 된것이 아니라 새로 지정됐기 때문에 다른 set가 되었기 때문이다.

 

그렇게 고민하다가 다른 방법을 떠올렸다. 모든 노드간에 부모 dictionary를 생성하고, 가장 최종부모다 같으면 cycle 아니면 최종부모를 같게 설정해주는 방법이었다.

 

코드는 아래와 같다.

 

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

N,M = map(int,input().split())

parent = {i:i for i in range(N)}

def findparent(x):
  if parent[x] == x:
    return x
  else:
    parent[x] = findparent(parent[x])
    return parent[x]  

result = 0
for i in range(1,M+1):
  x,y = sorted(map(int,input().split()))
  if result:
    continue
  xparent = findparent(x)
  yparent = findparent(y)
  if xparent == yparent:
    result = i
  else:
    parent[xparent] = yparent

print(result)

이 코드는 통과하였는데, 처음부터 통과되지는 않았다. 계속해서 80퍼 즈음에서 시간초과가 발생하였는데, 어떻게 해결할까 찾던 도중에 좋은 글을 발견하였다. https://www.acmicpc.net/board/view/94174

글 읽기 - 파이썬 런타임 에러, 메모리 초과, 시간 초과 나시는 분들을 위한 글입니다

"경로 압축"을 해주지 않고 무작정 계속 처음부터 부모노드를 찾아나간게 문제였다. 부모노드를 찾으면서 최종부모노드로 항상 갱신을 해주어야 시간이 절약되는 것이었다.

 

자세한 설명은 링크를 확인하자

 

 

오늘의 교훈) 경로 압축에 대해서 고민해보자