Funcia
Lv.2bfsdfsgridhash

서로 다른 모양의 섬

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

항공 사진으로 만든 바다 지도 grid가 주어집니다. grid[i]의 j번째 문자가 '1'이면 땅, '0'이면 바다입니다. 상하좌우로 이어진 땅 칸들의 묶음 하나를 섬 하나로 봅니다(대각선으로만 닿은 칸은 다른 섬입니다).

지도 제작자는 섬을 모양별로 분류하려고 합니다. 두 섬을 평행 이동만으로 정확히 겹칠 수 있으면 같은 모양으로 봅니다. 회전하거나 뒤집어야 겹쳐지는 섬은 다른 모양입니다.

서로 다른 섬 모양이 몇 가지인지 반환하세요. 섬이 하나도 없으면 0입니다.

입출력 예

gridresult
["11000", "11000", "00011", "00011"]1
["11011", "10000", "00001", "11011"]3
["010", "101", "010"]1

입출력 예 설명

예 1 — 2×2 정사각형 섬이 두 개 있고, 평행 이동하면 겹치므로 한 가지 모양입니다.

예 2 — 섬이 네 개입니다. 위 오른쪽과 아래 왼쪽의 가로 두 칸짜리 섬은 같은 모양입니다. 왼쪽 위의 ┌ 모양 섬과 오른쪽 아래의 ┘ 모양 섬은 회전하면 겹치지만 평행 이동만으로는 겹치지 않으므로 다른 모양입니다. 따라서 3가지입니다.

예 3 — 한 칸짜리 섬 네 개가 대각선으로만 닿아 있습니다. 모두 같은 모양입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(grid: string[]) → int

제한 사항

  • 1≤H=1 \le H = grid.length ≤1,000\le 1{,}000
  • 1≤W=1 \le W = grid[i].length ≤1,000\le 1{,}000, 모든 행의 길이는 같습니다.
  • 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)를 기록합니다. 시작 칸과 이웃을 보는 방향 순서가 항상 같으므로, 같은 모양의 섬은 같은 순서로 같은 좌표 목록을 만듭니다. (좌표를 정렬해서 써도 됩니다.)
  • 이 목록을 문자열이나 튜플로 바꿔 해시 집합에 넣습니다.

새 섬을 찾을 때마다 지금까지 모은 모양 전부와 하나씩 비교하면 섬이 많을 때 시간 초과가 납니다. 격자가 최대 10610^6칸이므로 재귀 DFS 대신 반복문(명시적 스택이나 큐)을 쓰는 것이 안전합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251184 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.