Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 고유 섬(Distinct Islands) 개수 세기: DFS 완전 정복

문제 개요

2차원 이진 배열 grid가 주어졌을 때, 섬(island)은 상하좌우(4방향)로 연결된 1(육지)들의 묶음을 의미합니다. 그리드의 네 가장자리는 모두 물로 둘러싸여 있다고 가정하며, 우리가 구해야 할 값은 서로 다른 섬의 개수입니다.

두 섬이 같은 섬으로 판정되는 조건은, 한 섬을 회전하거나 반전하지 않고 평행 이동만 했을 때 다른 섬과 정확히 일치하는 경우입니다.

입력 예시

그리드가 아래와 같이 주어졌다고 가정해 보겠습니다.

11011
10000
00001
11011

이때 출력은 3입니다. 왼쪽 위의 L자 모양 섬 1개, 길이 2인 가로 막대 형태의 섬 3개(모두 동일한 모양), 오른쪽 중간의 크기 1짜리 섬 1개가 존재하지만, 평행 이동으로 서로 겹칠 수 있는 섬들은 하나로 계산되기 때문입니다.

해결 접근 방식

핵심 아이디어는 DFS(깊이 우선 탐색)를 이용해 각 섬의 고유한 경로 시그니처(path signature)를 문자열로 기록하는 것입니다. 탐색을 시작할 때 's'를 추가하고, 이동할 때마다 방향 문자(r, l, d, u)를 덧붙인 뒤, 해당 분기의 탐색이 끝나면 'b'(백트래킹)를 추가합니다. 이렇게 만들어진 문자열은 섬의 형태를 유일하게 식별하므로, 집합(set)에 저장해 중복을 제거하면 서로 다른 섬의 개수를 얻을 수 있습니다.

dfs() 함수의 동작 단계

  • 매개변수로 x, y, grid, temp(경로 문자열), c(방향 문자)를 받습니다.
  • x, y가 그리드 범위를 벗어나거나 grid[x][y]가 0이면 즉시 반환합니다.
  • grid[x][y]를 0으로 바꿔 방문 처리합니다.
  • temp에 현재 방향 문자 c를 추가합니다.
  • 오른쪽(r), 왼쪽(l), 아래(d), 위(u) 네 방향으로 재귀 호출합니다.
  • 재귀 호출이 모두 끝나면 temp에 'b'를 추가해 백트래킹 지점을 표시합니다.

메인 로직(numDistinctIslands)

  • 결괏값 ret을 0으로 초기화하고, 중복 확인용 집합 visited를 선언합니다.
  • 그리드의 모든 칸을 순회하며 육지(1)를 발견하면 빈 문자열 aux로 DFS를 시작합니다.
  • 완성된 경로 문자열 aux가 visited에 없다면 ret을 1 증가시키고 aux를 집합에 삽입합니다.
  • 순회가 끝나면 ret을 반환합니다.

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
    void dfs(int x, int y, vector < vector <int> >& grid, string& temp, char c){
       if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || !grid[x][y])
          return;
       grid[x][y] = 0;
       temp += c;
       dfs(x + 1, y, grid, temp, 'r');
       dfs(x - 1, y, grid, temp, 'l');
       dfs(x, y + 1, grid, temp, 'd');
       dfs(x, y - 1, grid, temp, 'u');
       temp += 'b';
   }
   int numDistinctIslands(vector<vector<int>>& grid) {
       int ret = 0;
       set<string> visited;
       for (int i = 0; i < grid.size(); i++) {
          for (int j = 0; j < grid[0].size(); j++) {
             if (grid[i][j]) {
                string aux = "";
                dfs(i, j, grid, aux, 's');
                if (!visited.count(aux)) {
                   ret++;
                   visited.insert(aux);
                }
            }
       }
   }
   return ret;
  }
};
main(){
   Solution ob;
   vector<vector<int>> v =
   {{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}};
   cout<<(ob.numDistinctIslands(v));
}

입력

{{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}}

출력

3

복잡도 분석

시간 복잡도: O(R×C). 그리드의 모든 칸을 한 번씩 확인하며, 각 칸은 DFS에 의해 최대 한 번만 탐색됩니다.

공간 복잡도: O(R×C). 방문 처리를 위해 그리드 자체를 수정하고, 경로 문자열과 집합에 최대 그리드 크기만큼의 데이터가 저장될 수 있습니다.