3차원 공간 탐험

면접 대비

시간 제한1초메모리 제한128 MB

요약
N x N x N 격자에서 면을 공유하는 '*' 블록끼리 이어진 덩어리의 개수를 센다.
난이도

쉬움10점 중 3점

유형
그래프, DFS, BFS, 구현
정답자
아직 제출이 없습니다

문제

Farmer John의 소들이 드디어 지구를 떠나 Moocraft를 타고 우주를 떠돌고 있습니다. 목성의 위성 Io에 있는 동료들에게 가려면 먼저 위험한 소행성대를 통과해야 합니다.

Bessie는 N×N×NN \times N \times N (1≤N≤1001 \le N \le 100) 크기의 우주 구역을 조종해 지나갑니다. 구역 안의 각 소행성은 면과 면이 맞닿아 연결된 1×1×11 \times 1 \times 1 크기의 암석 블록 덩어리입니다. 변(모서리)만 맞닿거나 꼭짓점만 맞닿은 두 블록은 서로 다른 소행성입니다.

이 구역에 있는 서로 다른 소행성의 개수를 세세요.

구역은 앞에서 뒤로 겹겹이 쌓인 NN개의 정사각형 조각(slice)으로 주어집니다. 각 조각은 N×NN \times N 격자이며, *는 암석 블록을, .는 빈 공간을 나타냅니다. 조각 ss, 행 rr, 열 cc에 있는 블록은 (s±1,r,c)(s\pm1, r, c), (s,r±1,c)(s, r\pm1, c), (s,r,c±1)(s, r, c\pm1) 위치의 블록과 면을 공유하며, 이렇게 연결된 블록들은 같은 소행성에 속합니다.

예를 들어 3×3×33 \times 3 \times 3 구역을 생각해 봅시다. M은 (1,1,1)(1,1,1)에 있는 Moocraft의 출발 위치, D는 (3,3,3)(3,3,3)에 있는 목적지를 나타냅니다. 이 표시는 지도의 방향을 잡기 위한 것일 뿐 문제 풀이에는 필요하지 않습니다.

   Close slice    Middle slice     Far Slice     Assembled with overlaps
     +---+            +---+          +---+                  +---+ Far
     |M..|            |..*|          |...|                  |...|
     |.*.|            |.*.|          |.*.|                +---+.|
     |...|            |*..|          |..D|                |..*|D|
     +---+            +---+          +---+              +---+.|-+
                                                        |M..|.|
                                                        |.*.|-+
                                                        |...|
                                                  Close +---+

눈으로 살펴보면 소행성은 세 개이며, 그중 하나는 구역 가운데를 곧게 관통합니다. 다음 그림은 각 블록이 속한 소행성의 번호를 표시한 것입니다.

                                 +---+ Far
                                 /|...|
                                / |.1.|
                               /  |...|
                              /   +---+
                             +---+   /
                            /|..3|  /
                           / |.1.| /
                          /  |2..|/
                         /   +---+
                        +---+   /
                        |...|  /
                        |.1.| /
                        |...|/
                  Close +---+

입력

  • 첫째 줄에 정수 NN (1≤N≤1001 \le N \le 100)이 주어집니다.
  • 이어지는 N2N^2개의 줄은 NN개의 조각을 순서대로 나타냅니다. 각 조각은 정확히 NN개의 문자로 이루어진 NN개의 줄로 주어지며, 각 문자는 *(암석 블록) 또는 .(빈 공간)입니다.
  • 첫째 줄 이후로, s⋅N+1s \cdot N + 1번째 줄부터 s⋅N+Ns \cdot N + N번째 줄까지(s=0,1,…,N−1s = 0, 1, \dots, N-1)가 조각 ss를 이룹니다. 한 조각 안에서 각 줄은 행, 줄 안의 각 문자는 열이며, 인접한 두 조각의 같은 행·열은 서로 정렬되어 면을 공유합니다.

출력

  • 구역에 있는 서로 다른 소행성의 개수를 정수 하나로 출력합니다.

예제1

  1. 예제 1

    입력
    3
...
.*.
...
..*
.*.
*..
...
.*.
...
    예상 출력
    3