백준 1717: 집합의 표현 (Python)

 

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

1717번: 집합의 표현

 

이코테에서 풀었던 문제 그대로 나왔다.

https://sssbin.tistory.com/193

그래서 알고리즘 다시 정리한다는 마음으로 내 손으로 직접 풀었지만 ,, 시간 초과로 실패

 

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    # 번호 작은 노드가 부모 - 번호 큰 노드가 자식
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n, m = map(int, input().split())

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

for _ in range(m):
    c, a, b = map(int, input().split())

    if c == 0: # 합집합
        union_parent(parent, a, b)
    else: # 같은 집합인지 확인
        if find_parent(parent, a) == find_parent(parent, b):
            print("YES")
        else:
            print("NO")

 

입력 값이 많으니까 (1 ≤ m ≤ 100,000)

시스템 입출력을 이용해서 값을 입력받도록 바꿨는데 (아래 코드 추가)

import sys
input = sys.stdin.readline

재귀 런타임 에러가 발생했다.

 

파이썬에서 재귀를 사용하는 문제는 기본으로 설정되어 있는 재귀 깊이가 작아서 재귀 깊이 제한을 풀어줘야 한다고 함,,

그리고 다시 내 코드랑 문제를 살펴보다가 놓친 부분을 발견했다.

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다.

parent 리스트 초기화를 인덱스 1부터 해줬는데 숫자가 0부터 시작.!!!! 그래서 재귀 제한 늘려주고 (n의 최대 범위로 설정) 리스트 초기화 부분 반복문 범위를 바꿔줬다.

 

# 추가
sys.setrecursionlimit(1000000)

# 수정
parent = [0] * (n+1)
for i in range(n+1):
    parent[i] = i

 

드디어 정.답. 😥

<최종 코드>

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    # 번호 작은 노드가 부모 - 번호 큰 노드가 자식
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n, m = map(int, input().split())

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

for _ in range(m):
    c, a, b = map(int, input().split())

    if c == 0: # 합집합
        union_parent(parent, a, b)
    else: # 같은 집합인지 확인
        if find_parent(parent, a) == find_parent(parent, b):
            print("YES")
        else:
            print("NO")