[BOJ] 백준 4195 친구 네트워크 (유니온 파인드 최적화 자바 풀이)

 

 

https://www.acmicpc.net/problem/4195

 

 

 

📌 문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

 

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

 

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

 

---

⚔ 제한 사항

 

 

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

 

 

출력 

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

 

예시 

// 입력 

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

 

// 출력

2
3
4
2
2
4

 

 

---

 

 

 

👀 문제 해석

소셜 네트워크에서 “친구 네트워크” 라는 개념을 다루는 문제다. 입력은 친구 관계가 생긴 순서대로 주어지는데, 한 줄마다 두 사용자가 새로 친구가 되었다는 의미다. 프로그램은 각 관계가 추가되자마자 그 둘이 속해 있는 전체 네트워크(= 친구 사슬이 연결돼 이동할 수 있는 집합)의 인원 수를 바로 출력해야 한다. 말하자면 “A와 B가 친구가 되었을 때, A–B가 포함된 연결 요소의 크기는?”을 실시간으로 계속 묻는 셈이다.

 

관계 수 F가 최대 100 000이라 입·출력 한 번당 거듭해서 O(N)만큼 선형 탐색을 돌면 곧바로 시간 제한 3초를 넘긴다. 결국 중복 이름을 빠르게 식별하고 두 집합을 빠르게 합치면서 크기를 관리해야 한다.

 

따라서 유니온 파인드 자료구조(Disjoint Set Union, Union-Find를 사용하되, DSU의 경로 압축 + 가중치 병합으로 한 쿼리를 α(N) ≈ O(1)에 처리해서, 대표 노드에 집합 크기를 저장해 즉시 출력해야만 시간 제한을 통과할 수 있다. 

 

즉, 한마디로 

대표적인 유니온 파인드(특히 최적화 문제가 모두 포함된) 문제이다. 

 

 

---

🔎 접근

 

“연결 요소 크기를 실시간으로 묻는다? 그리고 분리 집합이 있다?"

 

유니온 파인드 유형이라고 생각할 수 있는 대목이다.

 

이때, 두 가지 의문을 떠올릴 수 있다.

 

첫째, “이름이 문자열인데 배열 인덱스로 못 쓰잖아? → 어떻게 O(1)에 매핑하지?”

둘째, “집합을 합칠 때 크기를 즉시 알려면 어느 지점에 사람 수를 저장해야 깔끔할까?”

 

문자열 ID 문제: 해시맵으로 해결할 수 있다는 건 간단하게 떠올릴 수 있지만, ‘새 사람 등장 → ID 발급 → 배열 확장?’ 흐름이 자칫 꼬이면 성능이 깨진다. 그래서 ‘단일 테스트케이스 안에서 최대 몇 명까지 나올까?’를 먼저 계산해볼 필요가 있다. 관계 F가 100 000이면 최대 사람 수는 2 F = 200 000. “그렇다면 배열을 처음부터 2 F 크기로 잡아버리자!”—동적 확장은 애초에 없애버리기로.

 

집합 크기 보관 위치: 트리 구조의 루트에만 ‘size’를 저장하면 find 후에 곧장 꺼낼 수 있다. 그럼 병합할 때 크기를 업데이트해야 하는데, 여기서 또 고민. “size 작은 쪽을 큰 쪽 밑으로 붙여야 트리가 얕아지지!”—경로 압축만으로도 충분히 빠르지만 가중치 병합을 얹으면 안정적이다. 결국 “root 기준 size[]만 믿고 나머지는 무시”라는 원칙이 생겼다.

 

이렇게 ‘ID 매핑 → 루트 size 보관 → 가중치 union’ 세 단계를 확정시킬 수 있다. 엣지 케이스도 고려해볼 수 있을까? 

 

한 가지 생각해볼 만한 엣지 케이스는, 이미 친구였던 두 사람을 union 하는 케이스이다. 이때는 find 결과가 같으니 size 그대로 반환하면 된다.

 

이제 이 접근을 토대로 풀이 아이디어를 구체화해보자. 

 

---

💡 풀이 아이디어 

 

“이름을 번호표로 바꿔서, 같은 번호표끼리 모으고, 모인 사람 수를 리더 한 곳에만 써 둔다.”

 

 

1. 핵심 설계 

 

1) 사람 이름 → 정수 ID 매핑

 

이름이 문자열이기 때문에 직접 배열 인덱스로 쓸 수 없다. HashMap<String,Integer>를 만들어 새 사람이 등장할 때마다 연속된 정수 ID(0, 1, 2, …)를 부여한다.

 

들어온 이름	새 번호?	결과
“Fred”	yes → 0	Fred → 0
“Barney”	yes → 1	Barney → 1
“Fred”	no	이미 0

 

2) 유니온-파인드

• parent[id] : 해당 노드의 대표(parent).
• size[id] : 그 대표 노드가 뿌리인 집합의 크기.
• find(x)는 경로 압축, union(x,y)는 랭크 대신 size를 이용해 집합을 병합하고, 병합 후 새 집합 크기를 반환다.

 

3) 질문에 대한 출력 시점

친구 관계 한 줄을 읽을 때마다 union을 호출하고 즉시 집합의 크기를 출력해야 한다.

2. 자료구조 설계

Map<String,Integer> id;   // 이름 → ID
int[] parent;             // parent[ID]
int[] size;               // 집합 크기
int nextId = 0;           // 다음에 부여할 ID

 

ID의 최댓값은 한 테스트케이스에서 등장하는 서로 다른 사람 수 ≤ 2 × F (관계마다 두 명이므로).

 

parent와 size는 길이를 2*F로 잡으면 충분하다.

 

 

3. 알고리즘 설계 - 유니온-파인드

parent[]   ←  각 사람이 “윗사람” 번호를 기억
size[]     ←  그 윗사람이 대표인 무리(네트워크) 인원 수

루트(root)	맨 꼭대기 사람(스스로가 부모)
find(x)	x가 속한 루트를 찾아 위로 쭉~ 올라감. 가면서 “바로 루트를 가리켜!” 라고 길을 지름길(경로 압축) 로 바꿔 줌.
union(a,b)	a무리와 b무리를 합침. 작은 무리를 큰 무리 밑으로 붙여서 나무가 덜 기울어지게 함.

 

 

 

3. 풀이 플로우 

초기 상태
A   B   C   D    (size=1씩)

union(A,B)
A-B  C  D        (루트 A, size[A]=2)

union(C,D)
A-B  C-D         (루트 C, size[C]=2)

union(B,C)
A-B-C-D          (루트 A, size[A]=4)

이제 A·B·C·D 중 누구에게 find를 해도 같은 루트(=A)이며
size[A] = 4 → 네트워크 인원 즉시 출력!

 

 

 

🚀 코드 구현 

public class Main {

    private static int[] parent;           // 각 정점의 부모
    private static int[] size;             // 루트에 저장되는 집합 크기
    private static Map<String, Integer> idMap; // 이름 → ID 매핑
    private static int nextId;             // 다음에 부여할 ID


    public static void main(String[] args) throws IOException {
       System.setIn(new FileInputStream("fundamentals/src/test/java/template/Boj/input.txt"));
       StringBuilder output = new StringBuilder();
       BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

       int testCaseCount = Integer.parseInt(bufferedReader.readLine());

       for (int testCaseIndex = 0; testCaseIndex < testCaseCount; testCaseIndex++) {
          int friendshipCount = Integer.parseInt(bufferedReader.readLine());

          parent = new int[friendshipCount * 2];
          size = new int[friendshipCount * 2];
          idMap = new HashMap<>(friendshipCount * 2);
          nextId = 0;

          for (int index = 0; index < friendshipCount * 2; index++) {
             parent[index] = index;   // 자기 자신을 부모로
             size[index] = 1;         // 집합 초기 크기 1
          }

          for (int line = 0; line < friendshipCount; line++) {
             StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
             String nameA = stringTokenizer.nextToken();
             String nameB = stringTokenizer.nextToken();

             int idA = getId(nameA);
             int idB = getId(nameB);

             int networkSize = union(idA, idB);
             output.append(networkSize).append('\n');
          }
       }

       System.out.print(output.toString());
    }

    /**
     * 이름을 ID로 변환한다. 처음 보는 이름이면 새 ID를 부여한다.
     */
    private static int getId(String name) {
       Integer existingId = idMap.get(name);
       if (existingId == null) {
          existingId = nextId;
          idMap.put(name, existingId);
          nextId++;
       }
       return existingId;
    }

    /**
     * find: 루트를 찾는다. (경로 압축 적용)
     */
    private static int find(int node) {
       if (parent[node] != node) {
          parent[node] = find(parent[node]);
       }
       return parent[node];
    }

    /**
     * union: 두 집합을 병합하고 병합 후 집합 크기를 반환한다. (트리 높이 최소화 적용)
     */
    private static int union(int nodeA, int nodeB) {
       int rootA = find(nodeA);
       int rootB = find(nodeB);

       if (rootA == rootB) {
          return size[rootA];
       }

       if (size[rootA] < size[rootB]) {
          int temporary = rootA;
          rootA = rootB;
          rootB = temporary;
       }

       parent[rootB] = rootA;
       size[rootA] += size[rootB];

       return size[rootA];
    }
}

 

 

문제의 다음과 같은 입력에 대해서 어떻게 동작하는지 살펴보자. 

 

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

 

먼저 첫 번재 테스트 케이스이다.

 

단계	추가된 친구	새로 발급된 ID	parent[]	size[]	출력
0	― (시작)	―	[0,1,2,3]*	[1,1,1,1]*	—
1	Fred Barney	Fred → 0, Barney → 1	[0,0]	[2,1]	2
2	Barney Betty	Betty → 2	[0,0,0]	[3,1,1]	3
3	Betty Wilma	Wilma → 3	[0,0,0,0]	[4,1,1,1]	4

 

* 배열 길이는 2 × F = 6 이지만, 아직 쓰이지 않은 뒤쪽 인덱스는 생략

 

괄호 안 숫자는 루트만 의미가 있다 (예: parent[1]=0 → Barney 의 루트는 Fred).

 

단계 0:   Fred   Barney   Betty   Wilma
           0       1        2       3         (4개의 점, 전부 size=1)

단계 1:   Fred(0)
            └─ Barney(1)                size[0]=2

단계 2:   Fred(0)
            ├─ Barney(1)
            └─ Betty(2)                 size[0]=3

단계 3:   Fred(0)
            ├─ Barney(1)
            ├─ Betty(2)
            └─ Wilma(3)                 size[0]=4

 

첫 번째 케이스에서는 별도 분리 집합이 생기지 않고, 하나의 집합 내의 root에 모두 합쳐지는 방식으로 끝난다. 

 

두 번째 케이스는 별도 분리 집합이 생긴다. 

 

단계	추가된 친구	새로 발급된 ID	parent[]	size[]	출력
1	Fred Barney	Fred → 0, Barney → 1	[0,0]	[2,1]	2
2	Betty Wilma	Betty → 2, Wilma → 3	[0,0,2,2]	[2,1,2,1]	2
3	Barney Betty	―	[0,0,0,0]	[4,1,2,1] → [4,1,4,1]	4

 

 

① Fred Barney가 추가되는 순간

• 해시맵에 두 사람이 처음 등장하므로 ID 0, 1이 차례로 발급된다.
• parent[0]과 parent[1]은 각자 자신을 가리키고 있다가 union을 거치며 둘 중 아무 쪽이나 루트가 된다(우리 코드는 크기가 같으면 앞쪽 ID를 루트로 둔다). 결국 루트 0 아래에 1이 붙으면서 size[0]이 2로 늘어난다.
• 네트워크 인원이 2명이므로 첫 출력값이 2이다.

② Betty Wilma가 추가되는 순간

• 이번에도 새 이름 두 개가 등장해 ID 2, 3이 발급되고, ID 2가 루트인 또 다른 집합이 만들어진다.
• parent[2]=2, parent[3]이 2를 향하게 조정되며 size[2]=2가 된다.
• 이 시점에는 {Fred, Barney}와 {Betty, Wilma}라는 서로 분리된 두 덩어리가 존재한다. 따라서 두 번째 출력값도 각각의 집합 규모 그대로 2이다.

③ Barney Betty가 추가되는 순간

• find(Barney)는 경로 압축을 통해 루트 0을, find(Betty)는 루트 2를 돌려준다.
• 이제 서로 다른 두 집합을 합쳐야 하니, 크기를 비교해 작은 집합(2명짜리 루트 2)을 큰 집합(2명짜리 루트 0) 아래로 붙인다. 루트가 동일 규모일 땐 ID가 더 작은 0을 루트로 택한다.
• 결과적으로 parent[2]=0, parent[3]은 이미 2를 따라가고 있으므로 이 순간 트리의 꼭대기는 0 하나로 통일된다.
• size[0]은 기존 2 + 붙는 쪽 2 = 4로 증가한다. size[2]는 더 이상 의미가 없지만, 루트가 아닌 노드의 size는 참조하지 않으니 깨끗이 무시해도 된다.
• 최종적으로 4명이 한 네트워크에 모였으므로 세 번째 출력값이 4가 된다.

 

단계 0:   Fred   Barney   Betty   Wilma
           0       1        2       3         (4개의 점, 전부 size=1)

단계 1:   Fred(0)
            └─ Barney(1)                size[0]=2

단계 2:   Fred(0)
            ├─ Barney(1)
            └─ Betty(2)                 size[0]=3

단계 3:   Fred(0)
            ├─ Barney(1)
            ├─ Betty(2)
            └─ Wilma(3)                 size[0]=4

 

 

두 번째 테스트 케이스에서는 이처럼 “2 명짜리 네트워크 두 개 → 4 명짜리 하나”로 병합된다. 특히 마지막에 Barney와 Betty를 연결하면서 parent 배열이 0을 공통 루트로 갱신되고, 루트 0의 size가 4로 점프한다. 덕분에 이후 누구에게 find()를 호출해도 한 번에 0을 얻고, size[0]만으로 집합 크기를 즉시 알 수 있다.

 

 

 

---

 

⏱️ 시간 복잡도

 

마지막으로 시간 복잡도만 간단히 살펴보자.

 

• ID 매핑
  HashMap 에서 이름 → ID 조회·삽입이 평균 O(1)
• find / union
  경로 압축 + 가중치(크기) 병합을 적용한 DSU의 한 연산은
  O(α(N)) — 아커만 역함수 α는 10⁵ 건에서도 사실상 상수.
• 전체 관계 F (≤ 100 000) 처리
  F 번 각각
  ID 조회 2 회 + union 1 회 → O(F α(N)) ≈ O(F)

따라서 최종 시간 복잡도는 O(∑ F), 즉 각 케이스의 F를 모두 합한 값에 선형적이다.

 

---

 

 

 

 

 

유니온 파인드 참고 글

 

https://upcurvewave.tistory.com/750

집합, 유니온 파인드 알고리즘, 개념과 구현 + 최적화 + 활용 예시까지 (시간 복잡도와 재귀 호출