Algorithm | [백준 1717] 집합의 표현 (그래프, Python)
[백준 1717] 집합의 표현
그래프 알고리즘 - 유니온 파인드
문제
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.
출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)
예제
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
예제 출력
NO
NO
YES
문제 풀이
유니온 파인드 알고리즘의 기본 문제였다!
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
# 부모 노드를 찾는 함수
def getParent(parent, x):
if parent[x] == x: return x
parent[x] = getParent(parent, parent[x])
return parent[x]
# 두 부모 노드를 합치는 함수
def unionParent(parent, a, b):
a = getParent(parent,a)
b = getParent(parent,b)
if a < b: parent[b] = a
else: parent[a] = b
# 같은 부모를 가지는지 확인
def findParent(parent, a, b):
a = getParent(parent, a)
b = getParent(parent, b)
if a == b : print("YES")
else: print("NO")
n, m = map(int, input().split())
parent = [0] * (n+1)
for i in range(n+1):
parent[i] = i
for _ in range(m):
n, a, b = map(int, input().split())
if n == 0: unionParent(parent, a, b)
else: findParent(parent, a, b)
📍중요한 부분은 sys.setrecursionlimit(100000)
분명 로직은 맞는데 런타임에러가 발생했다!!
재귀로 풀다보니 최대 재귀 한도 에러가 발생! 파이썬은 재귀의 한도가 시스템의 안정을 위해 정해져 있고 그 한도를 푸는 방법이 있는데 그것이 바로 sys.setrecursionlimit(100000) 요거다.
Author And Source
이 문제에 관하여(Algorithm | [백준 1717] 집합의 표현 (그래프, Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@eujin/Algorithm-백준-1717-집합의-표현-그래프-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)