[코테연습] 947. Most Stones Removed with Same Row or Column

- 유니온-파인드 문제

 

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/description/?envType=daily-question&envId=2024-08-29

 

- 문제분석

1. int[][] stone 배열에는 각 돌 (Stone) 에 대한 위치값 ([x,y]) 이 정해져있다.

2. 각 stone 의 row 와 col 에 돌이 이미 놓여져있다면 해당 stone 을 제거할 수 있다.

2-1. 예를들어 [1,1] 에 stone 이 놓여져있고, [1,0] 에 stone 이 놓여져있다면 동일한 행에 Stone 이 놓여져있으므로 [1,1] 의 Stone 을 제거한다.

3. 해당 방법으로 가장 Stone을 많이 제거할 수 있는 방법을 찾아라.

 

- 문제풀이

1. union-find 알고리즘을 이용한다.

2. 큰 개념은 각 Stone 의 부모 ( int[] parent ) 를 정의하고, 부모를 서로 연결하여 동일한 Stone으로 엮어나가는 과정이다.

3. 우선 find 함수를 만든다.

3-1. find 함수는 유니온-파인드 알고리즘의 find의 구현.

3-2. int[] parent 를 자기자신으로 초기화한다.

3-3.부모 (int[] parent) node 에 없는 새로운 node 라면 count ( Stone 의 갯수 ) 를 늘린다.

4. union 함수를 만든다.

4-1. union 함수를 만들때, 이미 부모가 동일할 경우 ( find(x) == find(y) ) 에는 skip 하고, 동일하지 않은 경우에는 부모를 일치시킨 뒤에 count ( stone의 갯수 ) 를 줄여준다. ( stone 을 연결했다는 개념 )

5. row 를 stone[0] + 1, col 을 stone[1] + 10002 로 설정하여 Stone 을 가장 멀리 떨어져 있는 것부터 결합한다.

 

 

class Solution {

    int[] parent; // 부모 노드
    int count; // 연결된 Stone 의 총 갯수

    public int removeStones(int[][] stones) {
        parent = new int[20003];
        count = 0;
        for (int[] stone : stones) {
            union(stone[0]+1, stone[1] + 10002);
        }
        //전체의 Stone - 연결된 Stone
        return stones.length - count;
    }

    void union(int x, int y) {
        x = find(x);
        y = find(y);
        // 이미 서로 연결되어있는 경우에는 skip
        if (x == y) {
            return;
        }
        // 부모를 서로 연결시키고 연결된 Stone 의 총 갯수 감소
        if(x <= y) {
            parent[y] = x;
        } else {
            parent[x] = y;
        }
        count--;
    }

    int find(int x) {
        // 해당 node 를 처음 거치는 경우 연결된 Stone 의 총 갯수를 늘리고 자기자신으로 초기화한다. 
        if (parent[x] == 0) {
            parent[x] = x;
            count++;
        }
        //find 부모 확인 --> 자기자신일 경우 자신의 원소 반환.
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
}