[구현] 프로그래머스 LV.3 표 병합

SH·2025년 11월 16일

Union Find 구현 스터디 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/150366

🎯 문제 접근

50x50 크기의 고정된 표에서 셀의 값을 수정하고, 여러 셀을 병합(MERGE)하거나 병합을 해제(UNMERGE)하는 복잡한 연산을 시뮬레이션하는 문제입니다.

이 문제의 핵심은 MERGE와 UNMERGE 명령어를 어떻게 효율적으로 처리하느냐입니다.

MERGE 시 두 셀은 하나의 '그룹'으로 묶여야 하며 이 그룹은 단일 값을 공유합니다.
그룹 내의 어떤 셀을 참조하든(UPDATE, PRINT) 항상 '대표' 셀의 값에 접근해야 합니다.
UNMERGE 시 이 그룹을 다시 해체해야 합니다.

이처럼 여러 노드(셀)를 '그룹'으로 묶고, 각 그룹의 '대표'를 찾는 작업은 전형적인 Union-Find (분리 집합) 자료구조를 사용하기에 적합합니다.

자료구조 선택:
- 50x50 격자를 1차원 배열(크기 2501)로 펴서 관리합니다. (r, c) -> (r-1) * 50 + c
- parent[] 배열: Union-Find의 부모 정보를 저장합니다.
- arr[] (또는 values[]) 배열: 각 셀의 값을 저장합니다. 단, 값은 항상 그룹의 '루트(대표)' 노드 인덱스에만 저장합니다.
명령어 매핑:
- MERGE (r1, c1, r2, c2): union(pos(r1, c1), pos(r2, c2))
- UPDATE (r, c, value): find(pos(r, c))로 루트를 찾아 arr[root] = value
- PRINT (r, c): find(pos(r, c))로 루트를 찾아 arr[root] 값 출력
- UNMERGE (r, c): 가장 복잡. find(pos(r, c))로 루트를 찾은 뒤, parent 배열을 순회하며 루트가 같은 모든 셀의 연결을 끊고 parent[i] = i로 초기화합니다.
- UPDATE (val1, val2): arr 배열을 순회하며 val1을 val2로 바꿉니다. (루트 노드만 검사)

📋 문제 조건

표 크기: 50 x 50 = 2500 (고정)
인덱싱: 1-based (r, c)
초기 상태: 모든 셀은 비어있고, 병합되지 않음.
명령어:
1. UPDATE r c value: (r, c)가 속한 그룹의 값을 value로 변경.
2. UPDATE value1 value2: value1 값을 가진 모든 셀(그룹)의 값을 value2로 변경.
3. MERGE r1 c1 r2 c2:
  - 두 셀이 같은 셀이면 무시.
  - 두 셀을 병합.
  - 값 우선순위: (r1, c1)의 값이 존재하면 그 값을, 없으면 (r2, c2)의 값을 따름.
4. UNMERGE r c:
  - (r, c)가 속한 그룹의 모든 병합을 해제.
  - (r, c) 셀은 그룹이 가지고 있던 값을 이어받음.
  - 나머지 해제된 셀들은 초기 상태(빈 값, 독립)로 돌아감.
5. PRINT r c:
  - (r, c)가 속한 그룹의 값을 출력.
  - 값이 없으면 "EMPTY" 출력.

🔎 문제 설계

1. 자료구조 및 헬퍼 함수

static int[] parent: Union-Find를 위한 부모 배열 (크기 2501)
static String[] arr: 셀의 값을 저장할 배열 (크기 2501)
- 값은 항상 각 그룹의 루트 인덱스(parent[i] == i)에만 저장됩니다.
find(int x): (경로 압축 적용)
- parent[x] == x (루트)가 아니면, parent[x] = find(parent[x])를 재귀 호출하여 부모를 루트로 갱신하고 루트를 반환합니다.
union(int a, int b): (MERGE 로직)
1. rootA = find(a), rootB = find(b)로 각 셀의 루트를 찾습니다.
2. rootA == rootB 이면 이미 같은 그룹이므로 return.
3. (r1, c1) 우선순위 규칙: arr[rootA] (a의 값)과 arr[rootB] (b의 값)를 가져옵니다.
4. parent[rootB] = rootA로 b 그룹을 a 그룹에 병합시킵니다.
5. a 그룹의 루트(rootA)에 값을 설정합니다. val1(a의 값)이 null이 아니면 val1을, null이면 val2(b의 값)를 arr[rootA]에 저장합니다.
6. arr[rootB] = null로 설정하여 더 이상 루트가 아닌 rootB의 값을 비웁니다.

2. 전체 프로세스 (solution 함수)

초기화:
- parent 배열을 parent[i] = i로 초기화합니다. (모든 셀이 자기 자신을 루트로 가짐)
- arr 배열은 자동으로 null로 초기화됩니다.
- PRINT 결과를 담을 List<String> aList 생성.
명령어 순회: commands 배열을 순회
- command.split(" ")로 명령어를 파싱.
- tmp[0] (명령어)에 따라 분기.
- 좌표 변환: (r, c) 좌표는 int idx = (r - 1) * 50 + c 공식을 사용해 1차원 인덱스로 변환합니다.
명령어별 로직:
- UPDATE (길이 4): int root = find(pos(r, c)). arr[root] = value.
- UPDATE (길이 3): val1, val2 추출. i를 1부터 2500까지 순회.
  - if (parent[i] == i && val1.equals(arr[i])): 루트 노드(parent[i] == i)이면서 값이 val1인 경우 arr[i] = val2로 변경.
- MERGE: idx1 = pos(r1, c1), idx2 = pos(r2, c2). union(idx1, idx2) 호출.
- UNMERGE:
  1. target = pos(r, c) (해제 기준 셀)
  2. root = find(target) (해제할 그룹의 루트)
  3. val1 = arr[root] (그룹의 현재 값 저장)
  4. arr[root] = null (루트 값 임시 제거)
  5. List<Integer> unMergeList 생성.
  6. i를 1부터 2500까지 순회: if (find(i) == root)이면 unMergeList.add(i). (병합 해제할 모든 셀을 찾음)
  7. unMergeList 순회: parent[idx] = idx (각 셀의 부모를 자기 자신으로 초기화하여 그룹 해제)
  8. arr[target] = val1 (기준 셀이었던 target에만 원래 값 부여)
- PRINT:
  1. root = find(pos(r, c)) (셀이 속한 그룹의 루트)
  2. s = arr[root] (루트의 값)
  3. s == null이면 aList.add("EMPTY"), 아니면 aList.add(s).
결과 반환: aList를 String[] 배열로 변환하여 반환.

📈 시간복잡도 분석

N = 총 셀의 개수 (50 * 50 = 2500)
K = 명령어의 개수 (최대 1,000)
Union-Find 연산 (find, union): 경로 압축(Path Compression)을 적용하면 시간 복잡도는 거의 상수 시간에 가까운 O(α(N)) (아커만 함수 역함수)입니다. O(1)로 봐도 무방합니다.

명령어별 시간 복잡도:
- UPDATE (r, c, value): find() 1회 -> O(1)
- UPDATE (value1, value2): 2500개 셀(루트) 순회 -> O(N)
- MERGE (r1, c1, r2, c2): union() 1회 -> O(1) (Amortized)
- UNMERGE (r, c):
  - find() 1회: O(1)
  - 모든 셀(N) 순회하며 find() 호출: O(N) (정확히는 O(N * α(N)))
  - unMergeList (최대 N) 순회: O(N)
  - 총 O(N)
- PRINT (r, c): find() 1회 -> O(1)
최종 시간 복잡도:
- 총 시간 복잡도는 모든 명령어의 합입니다.
- 최악의 경우는 K개의 명령어가 모두 UPDATE (value1, value2) 또는 UNMERGE인 경우입니다.
- 따라서 총 시간 복잡도는 O(K * N) 입니다.
- N = 2500, K = 1000 이므로, 2,500 * 1,000 = 2,500,000 입니다. 이는 1초 이내에 충분히 수행 가능한 연산량입니다.

💻 구현 코드

import java.util.*;

class Solution {
    static int[] parent;
    static String[] arr;

    // union: b를 a에 병합 (a 우선순위)
    public static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) {
            return;
        }

        String val1 = arr[rootA];
        String val2 = arr[rootB];

        // b의 부모를 a의 루트로 설정
        parent[rootB] = rootA;

        // 값 설정: val1 (a의 값)이 우선
        if (val1 != null) {
            arr[rootA] = val1;
        } else {
            arr[rootA] = val2;
        }
        
        // 이전 루트(b)의 값은 비움
        arr[rootB] = null;
    }

    // find: 루트 노드를 찾음 (경로 압축)
    public static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // (r, c) -> 1D index 변환
    public int getIndex(int r, int c) {
        return (r - 1) * 50 + c;
    }

    public String[] solution(String[] commands) {
        arr = new String[2501];
        parent = new int[2501];
        
        List<String> aList = new ArrayList<>();

        // 1. 초기화: 모든 셀이 자기 자신을 부모로 가짐
        for (int i = 1; i <= 2500; i++) {
            parent[i] = i;
        }

        for (String command : commands) {
            String[] tmp = command.split(" ");

            if (tmp[0].equals("UPDATE")) {
                if (tmp.length == 4) {
                    // UPDATE r c value
                    int r = Integer.parseInt(tmp[1]);
                    int c = Integer.parseInt(tmp[2]);
                    int root = find(getIndex(r, c));
                    arr[root] = tmp[3];
                } else if (tmp.length == 3) {
                    // UPDATE value1 value2
                    String val1 = tmp[1];
                    String val2 = tmp[2];
                    for (int i = 1; i <= 2500; i++) {
                        // 루트 노드만 검사
                        if (parent[i] == i && val1.equals(arr[i])) {
                            arr[i] = val2;
                        }
                    }
                }
            } else if (tmp[0].equals("MERGE")) {
                int r1 = Integer.parseInt(tmp[1]);
                int c1 = Integer.parseInt(tmp[2]);
                int r2 = Integer.parseInt(tmp[3]);
                int c2 = Integer.parseInt(tmp[4]);
                
                int idx1 = getIndex(r1, c1);
                int idx2 = getIndex(r2, c2);

                union(idx1, idx2);

            } else if (tmp[0].equals("UNMERGE")) {
                int r = Integer.parseInt(tmp[1]);
                int c = Integer.parseInt(tmp[2]);
                
                int target = getIndex(r, c);
                int root = find(target);
                String val1 = arr[root]; // 그룹의 값 저장

                arr[root] = null; // 루트 값 비우기

                List<Integer> unMerge = new ArrayList<>();
                // 1. 해제할 셀 목록 찾기
                for (int i = 1; i <= 2500; i++) {
                    if (find(i) == root) {
                        unMerge.add(i);
                    }
                }
                
                // 2. 해제 실행
                for (int idx : unMerge) {
                    parent[idx] = idx; // 부모를 자기 자신으로 초기화
                }

                arr[target] = val1; // (r, c) 셀에만 값 부여

            } else if (tmp[0].equals("PRINT")) {
                int r = Integer.parseInt(tmp[1]);
                int c = Integer.parseInt(tmp[2]);
                
                int root = find(getIndex(r, c));
                String s = arr[root];
                
                if (s == null) {
                    aList.add("EMPTY");
                } else {
                    aList.add(s);
                }
            }
        }

        String[] answer = new String[aList.size()];
        int idx = 0;
        for (String s : aList) {
            answer[idx] = s;
            idx++;
        }
        return answer;
    }
}

안녕하세요

이전 포스트

[구현] BOJ 14503 로봇청소기

다음 포스트