728x90 반응형 그래프2 [백준] 1717번: 집합의 표현 - java https://www.acmicpc.net/problem/1717유니온 파인드(Union-Find) 알고리즘은 합집합 찾기(Disjoint Set Union, DSU)라고도 불리며, 상호 배타적 집합을 관리하는 자료구조입니다. 주로 네트워크 연결, 동적 연결성 문제, 최소 신장 트리 알고리즘(크루스칼 알고리즘) 등에서 사용됩니다. 유니온 파인드 알고리즘은 다음 두 가지 주요 연산을 지원합니다:Find: 주어진 원소가 속한 집합을 찾는 연산. 대표 원소(루트)를 반환합니다.Union: 두 집합을 하나의 집합으로 합치는 연산. 1. 문제 해석 경로압축 알고리즘인 유니온 파인드를 우선적으로 공부를 한 다음에 학습을 시작했다. 이 알고리즘은 말 그대로 유니온이라는 함수와 파인드 함수 두가지로 이루어진 압축 알고.. 2024. 7. 17. [백준] 11724번: 연결 요소의 개수 - python https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 그래프 문제를 많이 풀어본적이 없어서 구현을 어떻게 해야할지 애를 많이 썻던 문제 아이디어 간선의 개수를 gragh 리스트에 전부 저장을 해준 뒤 방문 유무를 체크하면서 BFS로 색칠을 해준다. 그 후 cnt값을 계속 증가시키면서 최종 cnt를 출력하는 방식으로 구현하였다. from collections import deque imp.. 2024. 4. 5. 이전 1 다음 728x90 반응형
