Lv.2bfsdfsgridhash
서로 다른 모양의 섬
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
항공 사진으로 만든 바다 지도 grid가 주어집니다. grid[i]의 j번째 문자가 '1'이면 땅, '0'이면 바다입니다.
상하좌우로 이어진 땅 칸들의 묶음 하나를 섬 하나로 봅니다(대각선으로만 닿은 칸은 다른 섬입니다).
지도 제작자는 섬을 모양별로 분류하려고 합니다. 두 섬을 평행 이동만으로 정확히 겹칠 수 있으면 같은 모양으로 봅니다. 회전하거나 뒤집어야 겹쳐지는 섬은 다른 모양입니다.
서로 다른 섬 모양이 몇 가지인지 반환하세요. 섬이 하나도 없으면 0입니다.
입출력 예
| grid | result |
|---|---|
["11000", "11000", "00011", "00011"] | 1 |
["11011", "10000", "00001", "11011"] | 3 |
["010", "101", "010"] | 1 |
입출력 예 설명
예 1 — 2×2 정사각형 섬이 두 개 있고, 평행 이동하면 겹치므로 한 가지 모양입니다.
예 2 — 섬이 네 개입니다. 위 오른쪽과 아래 왼쪽의 가로 두 칸짜리 섬은 같은 모양입니다. 왼쪽 위의 ┌ 모양 섬과 오른쪽 아래의 ┘ 모양 섬은
회전하면 겹치지만 평행 이동만으로는 겹치지 않으므로 다른 모양입니다. 따라서 3가지입니다.
예 3 — 한 칸짜리 섬 네 개가 대각선으로만 닿아 있습니다. 모두 같은 모양입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(grid: string[]) → int
제한 사항
-
grid.length -
grid[i].length, 모든 행의 길이는 같습니다. grid[i]는'0'과'1'로만 이루어져 있습니다.
기대 복잡도
- 시간
- O(HW)
- 공간
- O(HW)
입출력 예
| grid | 기대 출력 |
|---|---|
["11000","11000","00011","00011"] | 1 |
["11011","10000","00001","11011"] | 3 |
["010","101","010"] | 1 |
힌트
힌트
섬마다 **평행 이동에 무관한 표현(서명)**을 만들어 해시 집합에 넣으면, 집합의 크기가 답입니다.
- 행 우선으로 격자를 훑다가 처음 만나는 땅 칸
(r0, c0)에서 BFS/DFS를 시작합니다. - 방문하는 칸마다
(r - r0, c - c0)를 기록합니다. 시작 칸과 이웃을 보는 방향 순서가 항상 같으므로, 같은 모양의 섬은 같은 순서로 같은 좌표 목록을 만듭니다. (좌표를 정렬해서 써도 됩니다.) - 이 목록을 문자열이나 튜플로 바꿔 해시 집합에 넣습니다.
새 섬을 찾을 때마다 지금까지 모은 모양 전부와 하나씩 비교하면 섬이 많을 때 시간 초과가 납니다. 격자가 최대 칸이므로 재귀 DFS 대신 반복문(명시적 스택이나 큐)을 쓰는 것이 안전합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1184 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |