Number of Distinct Islands

친구의 프리미엄 계정을 빌려서 문제를 풀고 있다 재밌는 문제를 발견했다. Distinct Islands, 즉 독립적인 섬의 숫자를 출력하면 되는 문제다. 그냥 단순하게 DFS를 사용해서 섬을 출력하는게 아니고 독립적인 섬의 "모양"이 같다면 그 섬들은 하나의 섬으로 취급해야 한다.

이런 문제는 도형의 모양을 잡는게 중요하지만 어떻게 해야할까? 좀 어려운 방법으로는 커다란 도형을 그려서 위치를 잡아주고 비교할 수도 있지만 이 문제에서는 좀 더 새로운 방법을 배웠다.각 섬을 탐색할때 섬의 좌표를 U,D,R,L 등으로 표현해서 같은 방향을 가진 섬은 좌표에 상관없이 같은 모양의 섬이다.

첫번째 예시에서도 서로 다른 좌표에 같은 모양의 도형이 있지만 실제로 계산해보면은 첫번쨰 도형은 DRU 두번째 도형도 DRU 형식이다. 그런데 문제점은 SET로 계산을 한다해도 모양은 다른데 순서는 같은 섬이 존재할 수 있기에 각 DFS 가 끝날때마다 X와 같은 표시를 남겨둬야 모든 케이스를 통과할 수 있다.

class Solution {
public:
    void dfs(int i, int j, vector<vector<int>>& grid, vector<char>& tmp, set<vector<char>>& dSet, char d){
        if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1) return; 
        grid[i][j] = 2; 
        
        tmp.push_back(d); 

        dfs(i + 1, j, grid, tmp, dSet, 'D'); 
        dfs(i -1, j , grid, tmp, dSet, 'U'); 
        dfs(i,j +1, grid, tmp, dSet, 'R'); 
        dfs(i,j -1, grid, tmp, dSet, 'L'); 

        tmp.push_back('X');
    }
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        set<vector<char>> dSet; 
        vector<char> tmp; 
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 1){
                    dfs(i,j,grid,tmp,dSet,'S'); 
                    dSet.insert(tmp); 
                    tmp.clear(); 
                }
            }
        }

        for(vector<char> t : dSet){
            for(char c : t){
                cout << c << ' '; 
            }
            cout << endl; 
        }
        return dSet.size(); 
    }
};