문제 개요
비어 있지 않은 2차원 이진 배열 grid가 주어진다고 가정해 보겠습니다. 여기서 섬(island)은 상하좌우 4방향으로 연결된 1(육지)들의 그룹을 의미하며, 격자의 네 가장자리는 모두 물로 둘러싸여 있다고 가정합니다.
목표는 고유한 섬의 개수를 세는 것입니다. 두 섬이 다음 조건 중 하나라도 만족하면 서로 같은 섬으로 간주합니다.
- 모양이 완전히 동일한 경우
- 90도, 180도 또는 270도 회전했을 때 모양이 동일한 경우
- 좌우 방향 또는 상하 방향으로 반사했을 때 모양이 동일한 경우
예를 들어 입력이 다음과 같다면,
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
출력은 1입니다. 왼쪽 위의 꺾인 모양 섬과 오른쪽 아래의 섬은 회전하면 동일한 형태가 되기 때문에 하나의 고유한 섬으로 계산됩니다.
풀이 접근 방식
핵심 아이디어는 각 섬의 좌표 목록을 정규화(canonical form)하는 것입니다. 회전과 반사로 만들 수 있는 모든 변형을 생성한 뒤 그중 사전순으로 가장 작은 형태를 대표값으로 삼으면, 회전이나 반사와 무관하게 같은 섬은 항상 동일한 대표값을 갖게 됩니다.
전체 흐름은 다음과 같습니다.
- DFS로 섬 찾기: 아직 방문하지 않은 육지(1)를 발견하면 DFS로 연결된 모든 칸의 좌표를 수집합니다.
- 8가지 변형 생성: 수집한 좌표에 대해 회전 4가지 × 반사 2가지로 만들 수 있는 8가지 변형을 생성합니다.
- 정렬 후 원점 이동: 각 변형의 좌표를 정렬하고, 첫 번째 좌표를 기준으로 평행 이동해 (0, 0)에서 시작하도록 만듭니다.
- 대표 형태 선택: 8가지 변형을 정렬해 가장 작은 것을 대표 형태로 사용하고, 집합(set)에 넣어 중복을 자동으로 제거합니다.
단계별 상세 설명
1. dfs() 함수
- 좌표를 저장할 맵 m을 정의합니다. m[idx]에는 idx번째 섬에 속한 좌표들이 저장됩니다.
- dfs(i, j, grid, idx)는 i, j가 격자 범위를 벗어나거나 grid[i][j]가 0이면 즉시 종료합니다.
- grid[i][j]를 0으로 바꿔 재방문을 방지하고, m[idx]의 끝에 {i, j}를 추가합니다.
- 이어서 dfs(i+1, j), dfs(i-1, j), dfs(i, j-1), dfs(i, j+1) 네 방향으로 재귀 호출합니다.
2. norm() 함수 (정규화)
- 좌표 쌍을 담는 2차원 배열 s를 8개 행으로 정의합니다.
- v의 각 좌표 (x, y)에 대해 다음 8가지를 각각 s[0]~s[7]에 추가합니다.
{x, y}, {x, -y}, {-x, y}, {-x, -y}, {y, x}, {y, -x}, {-y, x}, {-y, -x} - 각 s[i]를 정렬합니다.
- 정렬된 각 s[i]에서 첫 번째 좌표를 기준으로 나머지 좌표를 빼서 평행 이동하고, s[i][0]을 (0, 0)으로 만듭니다.
- s 전체를 정렬한 뒤 s[0], 즉 사전순으로 가장 작은 형태를 반환합니다.
3. 메인 로직
- 집합 pts를 정의하고 cnt를 1로 초기화합니다.
- 격자 전체를 순회하면서 grid[i][j]가 1이면 cnt를 1 증가시키고, dfs(i, j, grid, cnt)를 호출한 뒤 norm(m[cnt])의 결과를 pts에 삽입합니다.
- 최종적으로 pts의 크기를 반환합니다. 이것이 곧 고유한 섬의 개수입니다.
C++ 구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map < int, vector < pair <int, int> > > m;
void dfs(int i, int j, vector < vector <int> >& grid, int idx){
if (i >= grid.size() || j >= grid[0].size() || i < 0 || !grid[i][j])
return;
grid[i][j] = 0;
m[idx].push_back({ i, j });
dfs(i + 1, j, grid, idx);
dfs(i - 1, j, grid, idx);
dfs(i, j - 1, grid, idx);
dfs(i, j + 1, grid, idx);
}
vector < pair <int, int> > norm(vector < pair < int, int > > v){
vector<vector<pair<int, int> > > s(8);
for (int i = 0; i < v.size(); i++) {
int x = v[i].first;
int y = v[i].second;
s[0].push_back({ x, y });
s[1].push_back({ x, -y });
s[2].push_back({ -x, y });
s[3].push_back({ -x, -y });
s[4].push_back({ y, x });
s[5].push_back({ y, -x });
s[6].push_back({ -y, x });
s[7].push_back({ -y, -x });
}
for (int i = 0; i < s.size(); i++) {
sort(s[i].begin(), s[i].end());
}
for (int i = 0; i < s.size(); i++) {
for (int j = 1; j < v.size(); j++) {
s[i][j].first = s[i][j].first - s[i][0].first;
s[i][j].second = s[i][j].second - s[i][0].second;
}
s[i][0].first = 0;
s[i][0].second = 0;
}
sort(s.begin(), s.end());
return s[0];
}
int numDistinctIslands2(vector<vector<int>>& grid) {
set<vector<pair<int, int> > > pts;
int cnt = 1;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
cnt++;
dfs(i, j, grid, cnt);
pts.insert(norm(m[cnt]));
}
}
}
return pts.size();
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}};
cout << (ob.numDistinctIslands2(v));
}
입력
{{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}}
출력
1
복잡도 분석
격자의 크기를 R×C라고 할 때, 모든 칸을 한 번씩 방문하는 DFS에 O(R×C)의 시간이 걸립니다. 각 섬의 정규화 과정에서는 좌표 수를 k라 할 때 정렬 연산 O(k log k)가 8번 수행되므로, 전체 시간 복잡도는 대략 O(R×C log(R×C))입니다. 공간 복잡도는 좌표와 집합을 저장하기 위해 O(R×C)입니다.