[Lv.3] 표 병합

import java.util.ArrayList;
import java.util.List;

class Solution {
    static Point[][] points = new Point[51][51];
    public String[] solution(String[] commands) {
        List<String> answer=new ArrayList<>();
        for (int i = 1; i <= 50; i++) {
            for (int j = 1; j <=50; j++) {
                points[i][j]=new Point(i,j,"EMPTY");
            }
        }
        int cnt=1;
        for (String command : commands) {
            String[] s = command.split(" ");
            String order = s[0];
            if(order.equals("UPDATE")){
                if(s.length==4){
                    int r = Integer.parseInt(s[1]);
                    int c = Integer.parseInt(s[2]);
                    Point point = points[r][c];
                    for (Point[] pts : points) {
                        for (Point pt : pts) {
                            if(pt!=null){
                                //점들 중 현재 대상 점과 같은 그룹에 속해있거나 현재 점에게 속해있는 점들은 전부 값을 바꾼다.
                                if((pt.nowX==r&&pt.nowY==c)||(pt.nowX==point.nowX&&pt.nowY==point.nowY))
                                    pt.value=s[3];

                            }
                        }
                    }
                }else if(s.length==3){
                    for (Point[] point : points) {
                        for (Point pt : point) {
                            if(pt!=null&&pt.value.equals(s[1]))
                                pt.value=s[2];
                        }
                    }
                }
            }else if(order.equals("MERGE")){
                int r1 = Integer.parseInt(s[1]);
                int c1= Integer.parseInt(s[2]);
                int r2 = Integer.parseInt(s[3]);
                int c2 = Integer.parseInt(s[4]);
                //둘 다 값이 있을 때
                Point point1 = points[r1][c1];
                Point point2 = points[r2][c2];
                if(!point1.value.equals("EMPTY")){
                    //point1에 값이 있다면 무조건 이 값으로 설정
                    makeMerge(point1.value,r1,c1,r1,c1);
                    makeMerge(point1.value,r1,c1,r2,c2);
                }else if(!point2.value.equals("EMPTY")){
                    //1에는 없지만 point2에 값이 있다면 2의 값으로 설정
                    makeMerge(point2.value,r2,c2,r2,c2);
                    makeMerge(point2.value,r2,c2,r1,c1);
                }else{
                    //어차피 같으니 그냥 1로설정..
                    makeMerge(point1.value,r1,c1,r1,c1);
                    makeMerge(point1.value,r1,c1,r2,c2);
                }
            }else if(order.equals("UNMERGE")){
                int r=Integer.parseInt(s[1]);
                int c=Integer.parseInt(s[2]);
                //r,c가 이미 주체-> 값변동 안해도 됨 나머지만 empty

                for (Point[] point : points) {
                    for (Point pt : point) {
                        if(pt!=null&&pt.nowX==r&&pt.nowY==c){
                            if(pt.originX==r&&pt.originY==c){
                                //주체인 노드라면 값을 초기화하지 않아야 한다.
                                continue;
                            }
                            pt.nowX=pt.originX;
                            pt.nowY=pt.originY;
                            pt.value="EMPTY";
                        }
                    }
                }
                Point target = points[r][c];
                int a=target.nowX;
                int b=target.nowY;
                if(!(target.nowX==r&&target.nowY==c)){
                    for (Point[] point : points) {
                        for (Point pt : point) {
                            if(pt!=null&&pt.nowX== a&&pt.nowY==b){
                                pt.nowX=pt.originX;
                                pt.nowY=pt.originY;
                                if(pt.originX==r&&pt.originY==c){
                                    //값을 가질 노드는 초기화하지 않는다.
                                    continue;
                                }
                                pt.value="EMPTY";
                            }
                        }
                    }
                }


            }else{
                //print
                int r=Integer.parseInt(s[1]);
                int c=Integer.parseInt(s[2]);
                answer.add(points[r][c].value);
            }

        }
        return answer.toArray(new String[answer.size()]);
    }

    private void updateValue(String s, int r, int c) {
        Point point = points[r][c];
        point.value=s;
        if(!(point.nowX==point.originX&&point.nowY==point.originY)){
            updateValue(s,point.nowX,point.nowY);
        }

    }

    public void makeMerge(String value, int x,int y, int targetX,int targetY){
        Point target = points[targetX][targetY];
        if(target.nowX==target.originX&&target.nowY==target.originY){
            //종점 노드인 경우
            for (int i = 1; i <= 50; i++) {
                for (int j = 1; j <= 50; j++) {
                    Point pt = points[i][j];
                    if(pt.nowX==target.originX&&pt.nowY==target.originY){
                        pt.nowX=x;
                        pt.nowY=y;
                        pt.value=value;
                    }
                }
            }
            return;
        }
        int newX = target.nowX;
        int newY=target.nowY;
        target.nowX=x;
        target.nowY=y;
        target.value=value;
        makeMerge(value,x,y,newX,newY);
    }
    class Point{
        int nowX,nowY;
        int originX,originY;
        String value;

        @Override
        public String toString() {
            return "Point{" +
                    "nowX=" + nowX +
                    ", nowY=" + nowY +
                    ", originX=" + originX +
                    ", originY=" + originY +
                    ", value='" + value + '\'' +
                    '}';
        }

        public Point(int originX, int originY, String value) {
            this.originX = originX;
            this.originY = originY;
            this.value = value;
            this.nowX=this.originX;
            this.nowY=this.originY;
        }
    }
}

---

문제는 명확하게 설명되어 있다.

 

4가지 명령어가 주어지고 각 명령어마다 조건이 주어졌다.

반복 수가 최대 50*50이기에 시간상 문제는 크게 안될거라 생각해 명령어들에 대해 작업을 할 때 전체 점들에 대해 반복을 수행했다.

 

Update부터 살펴보면 UPDATE r c value인 경우 r,c의 값을 value로변경한다.

여기서, merge를 고려해야하기에 같은 그룹에 있는 모든 값을 value로 변경한다.

UPDATE value1 value2인 경우, value1을 가진 점들을 모두 value2로 변경한다. 

 

Merge의 경우 r1,c1점에 값이 있다면 해당 값을 r1c1이 속한 그룹과 r2,c2가 속한 그룹의 새로운 값으로 설정하고

값이 없다면 r2c2의 값을 두 그룹의 값으로 한다.

여기서 r1 c1그룹과 r2c2그룹을 합친다.

 

합치는 과정의 경우 makeMerge메소드를 보면 되는데,

만약 nowX,nowY가 original과 다르다면 해당 노드는 그룹에 속해있고 그룹의 주인이 아니기에 x,y를 그룹주인 좌표로 하는 새로운 그룹으로 now값을 변경하고 원래 자신의 그룹장이였던 노드에 대해 makeMerge를 재수행한다.

만약, now와 original이 같다면 해당 점은 1개 이상의 점으로 이루어진 그룹의 주인 점이다.

따라서, 해당 점을 부모 점으로 여기는 다른 노드들에 대해 (자신 포함) 새로운 부모 x,y를 now값으로 설정하고 값을 업데이트한다.

 

Unmerge의 경우 대상 점을 부모로 하는 점들에 대해 대상 점을 제외하고 나머지의 점들의 부모를 없애고(원래 자신의 점으로 설정하고) 값을 "EMPTY"로 설정한다. 또, 대상 점이 그룹 주인이 아닐 수 있기에 대상 점의 Now값과 같은 now값을 가지는 노드들에 대해 동일하게 부모를 없애고 값을 "EMPTY"로 설정하는 작업을 수행한다.

이렇게 되면 대상 점을 제외하고는 대상점이 속해있던 그룹 모두의 값이 EMPTY가 되고 모두 now값과 origin값이 같아지게 된다.

즉, 그룹이 해체된다.

 

print의 경우 그냥 r,c의 값을 바로 출력하면 된다.

---

나는 일단 위처럼 풀었다. 경우를 나누는것도 꽤 머리아팠고 머리속에서도 복잡해서 직접 테스트케이스를 몇개 넣어보고 디버그를 하며 문제를 풀었다. 거의 2시간 정도 걸렸는데, 이렇게 길게 풀어야 하는 문제인가 싶어 찾아보니 다들 "유니온-파인드" 알고리즘으로 풀었다고 했다. 접하지 못했던 알고리즘이라 전혀 몰랐는데 대충 보니 이 문제에 매우 적합한 알고리즘인 것 같다..

내일 시간이 되면 유니온 파인드 알고리즘 정리를 해봐야 겠다.