[JAVA] 프로그래머스 LEVEL3 표 병합

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

프로그래머스

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT > 표 병합

 

난이도: LEVEL3

 

풀이 설명

union - find 알고리즘을 사용해서 해당 문제를 풀었다.

 

나는 union - find 알고리즘을 MST - 최소 신장 트리 문제를 풀 때 접했어서 알고 있었다.

참고: MST 문제 해결 방법중 크루스칼 알고리즘에 union-find 알고리즘이 사용된다.

 

UNION - FIND

public static int find(int x){
    if(x == parent[x]){
        return x;
    }
    return parent[x] = find(parent[x]);
}
public static void union(int x, int y){
    x = find(x);
    y = find(y);
    if(x != y){
        if(x > y) parent[x] = y;
        else parent[y] = x;
    }
}

 

정답 코드

import java.util.*;
class Solution {
    static String [][] map = new String [50][50];
    static int [] parent = new int [2500];
    static final String EMPTY = "EMPTY"; 
    static ArrayList<String> answers = new ArrayList<>();
    public String[] solution(String[] commands) { // union - find 풀이 
        // 초기화 진행 
        for(int i = 0; i < 2500; i++){
            parent[i] = i;
        }
        // map 초기화 
        for(int i = 0; i < 50; i++){
            Arrays.fill(map[i], EMPTY);
        }
        // commands 로직 
        for(String next : commands){
            String [] split = next.split(" ");
            if(split[0].equals("UPDATE")){
                if(split.length == 3){ // "UPDATE value1 value2"
                    for(int i = 0; i < 50; i++){
                        for(int j = 0; j < 50; j++){
                            if(map[i][j].equals(split[1])) map[i][j] = split[2]; 
                        }
                    }
                }
                else{ // "UPDATE r c value"
                    int r = Integer.parseInt(split[1]) - 1;
                    int c = Integer.parseInt(split[2]) - 1;
                    String value = split[3];
                    int root = find(r * 50 + c);
                    for(int i = 0; i < 2500; i++){
                        if(parent[i] == root){
                            int x = i / 50;
                            int y = i % 50;
                            map[x][y] = value;
                        }
                    }
                }
            }
            else if(split[0].equals("MERGE")){ // "MERGE r1 c1 r2 c2"
                int r1 = Integer.parseInt(split[1]) - 1;
                int c1 = Integer.parseInt(split[2]) - 1;
                int r2 = Integer.parseInt(split[3]) - 1;
                int c2 = Integer.parseInt(split[4]) - 1;
                
                int root1 = find(r1 * 50 + c1);
                int root2 = find(r2 * 50 + c2);
                union(root1, root2);
                int root = find(root1);  // union 결과 
                
                String value = EMPTY;
                if(map[r1][c1].equals(EMPTY) && !map[r2][c2].equals(EMPTY)){
                    value = map[r2][c2];
                }
                else value = map[r1][c1];
                
                for(int i = 0; i < 2500; i++){
                    if(parent[i] == root1 || parent[i] == root2 || parent[i] == root){
                        parent[i] = root; // parent 전부 변경 
                        int x = i / 50;
                        int y = i % 50;
                        map[x][y] = value;
                    }
                }
            }
            else if(split[0].equals("UNMERGE")){ // "UNMERGE r c"
                int r = Integer.parseInt(split[1]) - 1;
                int c = Integer.parseInt(split[2]) - 1;
                String value = map[r][c];
                int root = find(r * 50 + c);
                for(int i = 0; i < 2500; i++){
                    if(parent[i] == root){
                        parent[i] = i; // 병합 해제 
                        int x = i / 50;
                        int y = i % 50;
                        map[x][y] = EMPTY;
                    }
                }
                map[r][c] = value;
            }
            else{ // "PRINT r c"
                int r = Integer.parseInt(split[1]) - 1;
                int c = Integer.parseInt(split[2]) - 1;
                answers.add(map[r][c]);
            }
        }
        // 정답 리턴 
        String[] answer = new String [answers.size()];
        for(int i = 0; i < answer.length; i++){
            answer[i] = answers.get(i);
        }
        return answer;
    }
    public static int find(int x){
        if(x == parent[x]){
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    public static void union(int x, int y){
        x = find(x);
        y = find(y);
        if(x != y){
            if(x > y) parent[x] = y;
            else parent[y] = x;
        }
    } 
}