목록union-find 알고리즘 (1)

영원히 남는 기록, 재밌게 쓰자

백준 [1717] 집합의 표현 (JAVA)

문제풀이union-find 알고리즘의 기본적인 문제여러 노드가 존재할 때 두 개의 노드를 선택해서 현재 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘 해당 개념을 잘 모르면 어려울 수 있는 문제였다. 두 개의 연산으로 이루어진다.find: x가 어떤 집합에 포함되어 있는지 찾는 연산union: x와 y가 포함되어 있는 집합을 합치는 연산 모든 집합을 돌면서 탐색을 진행하려고 했는데 그렇게하면 시간 초과가 날게 뻔했다.. find를 할때에는 재귀함수를 통해 부모를 찾는 과정을 거친다.정답코드package com.baekjoon.data_structure.p1717;import java.io.*;import java.util.*;public class Main { static int n, m; ..
Algorithm/백준 2024. 7. 9. 11:19
이전 Prev 1 Next 다음