읽기 전에 알아두면 좋아요
아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.
- JavaScript Union-Find: 경로 압축과 크기 합치기로 연결 상태 관리하기유니온 파인드는 두 원소가 같은 그룹인지 찾고 그룹을 합치는 구조입니다. 대표·경로 압축·크기 합치기로 연결 성분 수와 크기를 관리합니다.
- JavaScript 그래프 구현: 인접 리스트·인접 행렬 비교와 BFS그래프는 점인 정점과 점 사이의 연결인 간선으로 관계를 나타냅니다. 정점과 간선의 표현, 방문 상태를 관리하는 방법입니다.
개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.
과정 위치와 선택 복습 안내
과정 위치: 심화 선택 실습 · 문제
과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.
JavaScript로 문법·실행 복습하기 (선택)
개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.
Union-Find 연결 문제는 장치의 연결을 차례로 추가하면서 묶음의 어떤 정보를 구하나요?
장치의 연결을 차례로 추가하며 연결된 묶음의 수와 크기를 구하는 문제입니다. 배열·연결 관계·Union-Find의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.
적용 조건·범위: 입력은 위 계약을 만족한다고 가정합니다. 온라인 채점기는 제공하지 않으며 로컬 Node.js에서 JSON 입력으로 실행합니다.
본문 근거: AtCoder Library 공식 DSU 문서
[창작 문제] 이동 실험실의 연결 일지
장치 연결 요청마다 남은 네트워크 수와 요청 첫 장치의 네트워크 크기를 기록합니다. 중복 요청과 자기 연결은 새로운 합병이 아닙니다.
이 문제는 BlogFlow 자료구조 학습용으로 독립 창작했습니다. 외부 문제의 지문이나 테스트를 옮기지 않았습니다.
문제
이동 실험실은 n개의 장치를 처음에는 서로 분리해 둡니다. 관리자가 links의 순서대로 두 장치를 연결합니다. 각 요청을 처리한 직후 [전체 연결 성분 수, 요청 첫 장치가 속한 성분의 크기]를 일지에 남기세요. 이미 연결된 두 장치를 다시 연결하거나 같은 장치를 양쪽에 적은 요청도 일지 한 줄은 남겨야 합니다.
관련 구현 설명: JavaScript Union-Find: 경로 압축과 크기 합치기로 연결 상태 관리하기
입력·출력과 제약
JSON 객체 {n, links}를 표준 입력으로 받습니다. links의 각 원소 [a,b]는 두 장치 번호입니다.
요청 순서대로 두 정수를 담은 배열을 모아 JSON 배열 하나로 출력합니다. links가 비면 []입니다.
0 ≤ n ≤ 100,000, 0 ≤ links.length ≤ 100,000. 모든 번호는 정수이며 0 ≤ a,b < n입니다. n=0이면 links는 빈 배열입니다.
입력은 위 계약을 만족한다고 가정합니다. 온라인 채점기는 제공하지 않으며 로컬 Node.js에서 JSON 입력으로 실행합니다.
예시
예시 1 입력:
{"n":5,"links":[[0,1],[2,3],[1,2],[0,3],[4,4]]}예시 1 출력:
[[4,2],[3,2],[2,4],[2,4],[2,1]]예시 2 입력:
{"n":0,"links":[]}예시 2 출력:
[]힌트
성공한 합병 횟수만 전체 성분 수에서 빼세요. 성분 크기는 요청한 원소의 현재 대표를 통해 읽습니다.
정답과 해설
직접 풀어보기
먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.
AI 힌트
코드를 실행한 채점 결과가 아닌 AI의 코드 분석입니다.
해답·해설 보기
function solution(n, links) {
const parent = Array.from( {
length : n
},(_, i) => i), size = Array(n).fill(1);
const find = x => {
while (x !== parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let count = n;
const out = [];
for (const[a, b] of links) {
let ra = find(a), rb = find(b);
if (ra !== rb) {
if (size[ra] < size[rb])[ra, rb] = [rb, ra];
parent[rb] = ra;
size[ra] += size[rb];
count--;
}
out.push([count, size[find(a)]]);
}
return out;
}
solution(n, links)에 장치 수와 [a,b] 배열을 전달하며 [성분 수,크기] 배열들을 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
def solution(n, links):
parent, size = list(range(n)), [1] * n
def find(x):
while x != parent[x]:
parent[x] = parent[parent[x]]
x = parent[x]
return x
count = n
out = []
for a, b in links:
ra, rb = find(a), find(b)
if ra != rb:
if size[ra] < size[rb]: ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
count -= 1
out.append([count, size[find(a)]])
return out
solution(n, links)에 정수와 [a,b] 리스트를 전달하며 [성분 수,크기] 리스트들을 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
import java.util.*;
class Solution {
private int find(int[] parent, int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int[][] solution(int n, int[][] links) {
int[] parent = new int[n], size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
int count = n;
int[][] out = new int[links.length][2];
for (int i = 0; i < links.length; i++) {
int a = links[i][0], ra = find(parent, a), rb = find(parent, links[i][1]);
if (ra != rb) {
if (size[ra] < size[rb]) {
int temp = ra;
ra = rb;
rb = temp;
}
parent[rb] = ra;
size[ra] += size[rb];
count--;
}
out[i] = new int[] {
count, size[find(parent, a)]
};
}
return out;
}
}
Solution.solution(int n, int[][] links)는 요청별 {성분 수,크기}를 담은 int[][]를 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
#include <algorithm>
#include <array>
#include <functional>
#include <list>
#include <limits>
#include <memory>
#include <numeric>
#include <queue>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
vector < array < int, 2 >> solution(int n, const vector < array < int, 2 >> & links) {
vector < int > parent(n), size(n, 1);
iota(parent.begin(), parent.end(), 0);
auto find = [&](int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
int count = n;
vector < array < int, 2 >> out;
for (const auto & link : links) {
int a = link[0], ra = find(a), rb = find(link[1]);
if (ra != rb) {
if (size[ra] < size[rb]) swap(ra, rb);
parent[rb] = ra;
size[ra] += size[rb];
count--;
}
out.push_back( {
count, size[find(a)]
});
}
return out;
}
solution(int n, const vector<array<int,2>>& links)는 요청별 {성분 수,크기}를 담은 vector<array<int,2>>를 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
private int Find(int[] parent, int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int[][] Solve(int n, int[][] links) {
int[] parent = new int[n], size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
int count = n;
int[][] result = new int[links.Length][];
for (int i = 0; i < links.Length; i++) {
int a = links[i][0], ra = Find(parent, a), rb = Find(parent, links[i][1]);
if (ra != rb) {
if (size[ra] < size[rb]) {
int temp = ra;
ra = rb;
rb = temp;
}
parent[rb] = ra;
size[ra] += size[rb];
count--;
}
result[i] = new int[] {
count, size[Find(parent, a)]
};
}
return result;
}
}
Solution.Solve(int n, int[][] links)는 요청별 new int[]{성분 수,크기}를 담은 int[][]를 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
Node.js 24 CommonJS용 전체 풀이입니다. union-find-problem.cjs로 저장하세요. 클래스 선언, solve 함수, 표준 입력 처리가 모두 들어 있어 가이드 파일을 별도로 가져오지 않습니다. 예시 입력을 input.json에 저장하고 터미널에서 실행합니다.
Windows PowerShell:
Get-Content -Raw -Encoding UTF8 ./input.json | node ./union-find-problem.cjs
macOS / Linux:
node union-find-problem.cjs < input.jsonclass UnionFind {
constructor(n) {
if (!Number.isInteger(n) || n < 0 || n > 1_000_000) {
throw new RangeError('n은 0~1,000,000 정수여야 합니다.');
}
this.parent = Array.from({ length: n }, (_, i) => i);
this.sizes = Array(n).fill(1);
this.count = n;
}
check(x) {
if (!Number.isInteger(x) || x < 0 || x >= this.parent.length) {
throw new RangeError('원소 번호가 범위를 벗어났습니다.');
}
}
find(x) {
this.check(x);
let root = x;
while (this.parent[root] !== root) root = this.parent[root];
while (this.parent[x] !== x) {
const next = this.parent[x];
this.parent[x] = root;
x = next;
}
return root;
}
union(a, b) {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return false;
if (this.sizes[ra] < this.sizes[rb]) [ra, rb] = [rb, ra];
this.parent[rb] = ra;
this.sizes[ra] += this.sizes[rb];
this.count--;
return true;
}
same(a, b) { return this.find(a) === this.find(b); }
sizeOf(x) { return this.sizes[this.find(x)]; }
}
function solve({ n, links }) {
const d = new UnionFind(n);
return links.map(([a, b]) => {
d.union(a, b);
return [d.count, d.sizeOf(a)];
});
}
module.exports = { solve };
if (require.main === module) {
const input = JSON.parse(require('node:fs').readFileSync(0, 'utf8'));
console.log(JSON.stringify(solve(input)));
}links.map의 각 순회가 일지 한 줄에 대응합니다. union이 false여도 sizeOf(a)는 계산해야 합니다. 처음 두 요청으로 크기 2인 성분 두 개가 생기고 세 번째 요청으로 크기 4가 됩니다. 네 번째는 같은 성분 안의 중복 요청이므로 [2,4], 다섯 번째는 혼자 남은 장치 4의 자기 연결이므로 [2,1]입니다.
parent가 만드는 구조는 여러 개의 뿌리 있는 나무입니다. 루트만 parent[root]===root이고, 나머지는 같은 성분 안의 조상을 가리킵니다. 루트에서만 sizes[root]가 정확한 성분 크기입니다. 합쳐진 옛 루트의 sizes는 남아 있어도 더 이상 의미가 없으므로 sizeOf는 반드시 find를 먼저 호출합니다.
크기 합치기는 작은 나무의 루트를 큰 나무의 루트 아래에 붙입니다. 어떤 원소의 깊이가 1 증가했다면 그 원소가 속한 성분의 크기는 적어도 2배가 됩니다. 크기는 n을 넘지 않으므로 깊이는 O(log n)입니다. 합치기를 원소 a,b에 직접 적용하지 않고 대표 ra,rb에 적용해야 성분 일부만 떼어 붙이는 실수를 피할 수 있습니다.
초기화 O(n), q개 요청의 총 시간 O(n+qα(n)) 상환, 구조 O(n)와 반환 일지 O(q) 공간입니다. 개별 요청의 최악은 O(log n)입니다.
표본과 경계를 직접 확인하려면 다음 코드를 union-find-check.cjs로 저장하고 같은 폴더에서 node union-find-check.cjs를 실행하세요. assert가 맞으면 출력 없이 종료하고, 다르면 예외와 함께 실패합니다.
const assert = require('node:assert/strict');
const { solve } = require('./union-find-problem.cjs');
assert.deepEqual(
solve({
"n": 5,
"links": [
[
0,
1
],
[
2,
3
],
[
1,
2
],
[
0,
3
],
[
4,
4
]
]
}),
[[4,2],[3,2],[2,4],[2,4],[2,1]],
);
assert.deepEqual(
solve({
"n": 0,
"links": []
}),
[],
);연결 학습과 공식 자료
JavaScript Union-Find: 경로 압축과 크기 합치기로 연결 상태 관리하기에서 연산별 이유와 전체 복잡도를 이어서 확인할 수 있습니다. 다른 형식의 공식 연습은 AtCoder A – Disjoint Set Union를 참고하세요. 외부 문제의 정답이나 지문은 이 페이지에 복제하지 않았습니다.
공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.
이 문제를 푼 뒤 확인하기
풀이 직접 실행
본문 풀이에 예제 입력을 넣고, 입력을 바꿔 계산 결과를 비교합니다.
예제 크게 보기 (새 탭)같은 노드를 여러 번 합치는 경우와 연결 성분이 하나도 합쳐지지 않는 경우를 확인해 보세요.
본문의 예제와 이 반례를 직접 실행해 예상 출력과 비교하고, 결과가 다르면 입력 조건과 반복 범위를 다시 확인하세요.
이 글이 도움이 되었나요?
이어서 공부하기
체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 표본 하나에 더해 경계 입력과 작은 기준 풀이를 비교하고 왜 이 구조를 고르는지 설명하세요.
다음 추천 · 자료구조 개념: JavaScript Trie: Unicode 접두사 검색과 안전한 삭제 구현
권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.
원래 과정 목록 순서 (선택)
읽음 기록
읽음 — / 전체 58개 · 필수 58개
새 글 받아보기
RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.
