[백준 BOJ / Python] 1717번 집합의 표현
문제 0에서 n까지 숫자 한개로 이루어진 n+1개의 집합이 있다. 합집합 연산(0)과 두 원소가 같은 집합에 포함되는지 여부를 확인하는 연산(1)을 수행할 때, 같은 집합에 포함되면 yes, 아니면 no를 출력하는 문제이다. 연산은 연산종류(0,1), a원소, b원소 순서대로 입력된다. 풀이 이 문제는 각 원소가 포함된 집합의 대표 번호(부모 노드)를 저장함으로써 합집합 연산에서는 두 원소의 부모 노드를 더 작은 번호로 일치시켜주고 (union) 두 원소의 집합이 같은지 확인하는 연산에서는 부모 노드가 동일한지 확인하면 되기 때문에 (find) 분리집합 알고리즘으로 해결할 수 있다. 먼저 부모 노드들을 담을 parent(p) 리스트를 생성한다. 초기 부모 노드는 각 집합에 담겨있는 숫자의 번호로 초기화한..
Study/Coding Test
2023. 3. 31.