[2023 KAKAO BLIND RECRUITMENT] 표 병합

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

프로그래머스

 

유니온 파인드 + 구현 문제이다. 문제 풀이 아이디어 자체는 어렵지 않은데 구현 중간중간 실수하고 헷갈려서 헤맸다.. 특히 유니온 파인드를 통해 여러 집합을 하나의 집합으로 merge하고 반대로 unmerge하기도 하는데, 이때 생각을 잘 해야 한다.

• merge 된 노드 간에는 모두 최상위 부모 노드가 같다. 즉, parent[][] 값 자체는 다를 수 있지만, find() 메소드를 통해 얻게 되는 최상위 부모의 값은 같다. parent[][] 값과 find() 메소드 값의 차이를 구분해야 한다. parent[][] 값은 단순 직접적으로 연결된 부모 노드이고, 최상위 부모 노드를 찾기 위해선 find() 메소드를 사용해야 한다.
• merge 된 노드 간에는 모두 같은 값을 갖는다. 즉, graph[][] 값이 같다.
• 만약 1번 노드와 3번 노드를 합친다고 했을 때, 3번 노드의 parent 값을 1번 노드로 변경하는 식으로 처리하면 안된다. 우선 3번 노드의 최상위 부모 노드를 찾고, 최상위 부모 노드가 1번 노드를 가리키도록 해야 한다. 즉, 특정 노드가 어딘가의 부모 노드에 의해 병합된 노드일 수 있으니, 모든 처리에 있어서 해당 노드의 최상위 부모 노드를 먼저 찾아야 한다.
• 참고로 내가 정의한 Node라는 클래스에 대해 비교 연산을 하기 위해 hashCode와 equals를 재정의 해야 한다.

import java.util.*;

class Solution {

    String[][] graph = new String[51][51];
    Node[][] parent = new Node[51][51];

    public String[] solution(String[] commands) {

        initParent();

        List<String> list = new ArrayList<>();

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

            if (arr[0].equals("UPDATE")) {
                if (arr.length == 4) {
                    update(Integer.parseInt(arr[1]), Integer.parseInt(arr[2]), arr[3]);
                }
                if (arr.length == 3) {
                    update(arr[1], arr[2]);
                }
            }

            if (arr[0].equals("MERGE")) {
                merge(Integer.parseInt(arr[1]), Integer.parseInt(arr[2]),
                        Integer.parseInt(arr[3]), Integer.parseInt(arr[4]));
            }

            if (arr[0].equals("UNMERGE")) {
                unmerge(Integer.parseInt(arr[1]), Integer.parseInt(arr[2]));
            }

            if (arr[0].equals("PRINT")) {
                int y = Integer.parseInt(arr[1]);
                int x = Integer.parseInt(arr[2]);
                if (graph[y][x] == null) {
                    list.add("EMPTY");
                } else {
                    list.add(graph[y][x]);
                }
            }
        }

        String[] answer = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }

    private void initParent() {
        for (int i = 1; i < 51; i++) {
            for (int j = 1; j < 51; j++) {
                parent[i][j] = new Node(i, j); // 초기에는 자기 자신이 부모 노드
            }
        }
    }

    private Node find(int r, int c) {
        if (parent[r][c].y == r && parent[r][c].x == c) {
            return parent[r][c];
        }

        return parent[r][c] = find(parent[r][c].y, parent[r][c].x); // todo
    }

    private void update(int r, int c, String value) {
        // (r, c)의 최상위 부모 노드를 찾고, 해당 부모 노드의 모든 자식 노드의 값을 업데이터
        Node p = find(r, c);
        for (int i = 1; i < 51; i++) {
            for (int j = 1; j < 51; j++) {
                if (find(i, j).equals(p)) { // (i, j)의 최상위 부모 노드를 탐색해야 함
                    graph[i][j] = value;
                }
            }
        }
    }

    private void update(String value1, String value2) {
        for (int i = 1; i < 51; i++) {
            for (int j = 1; j < 51; j++) {
                if (graph[i][j] != null && graph[i][j].equals(value1)) {
                    graph[i][j] = value2;
                }
            }
        }
    }

    private void merge(int r1, int c1, int r2, int c2) {
        if (graph[r1][c1] != null) {
            union(r1, c1, r2, c2);
        } else {
            union(r2, c2, r1, c1);
        }
    }

    private void union(int r1, int c1, int r2, int c2) {
        String value = graph[r1][c1];

        // (r2, c2)의 최상위 부모 노드가 (r1, c1)의 최상위 부모 노드를 가리키도록
        Node baseP = find(r1, c1);
        Node childP = find(r2, c2);
        parent[childP.y][childP.x] = baseP;

        // 노드 값 업데이트
        for (int i = 1; i < 51; i++) {
            for (int j = 1; j < 51; j++) {
                if (find(i, j).equals(baseP)) {
                    graph[i][j] = value;
                }
            }
        }
    }

    private void unmerge(int r, int c) {
        String value = graph[r][c];
        Node p = find(r, c);
        for (int i = 1; i < 51; i++) {
            for (int j = 1; j < 51; j++) {
                if (find(i, j).equals(p)) {
                    parent[i][j] = new Node(i, j);
                    graph[i][j] = null;
                }
            }
        }
        graph[r][c] = value;
    }

    private static class Node {

        int y, x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return y == node.y && x == node.x;
        }

        @Override
        public int hashCode() {
            return Objects.hash(y, x);
        }
    }
}