h × w 크기의 격자(grid)가 주어졌다고 가정해 보겠습니다. 격자를 구성하는 각 칸은 흰색과 검은색 두 가지 유형으로 나뉘며, 흰색 칸은 '.'으로, 검은색 칸은 '#'으로 표현됩니다. 격자 안에는 여러 개의 검은색 칸이 모여 하나의 다각형을 형성하고 있으며, 우리가 구해야 하는 값은 바로 이 다각형이 가지고 있는 변의 개수입니다. 단, 격자의 가장 바깥쪽 칸들은 항상 흰색이라는 조건이 주어집니다.
예를 들어 h = 4, w = 4, grid = {"....", ".##.", ".##.", "...."}라는 입력이 주어진다면 출력은 4가 됩니다.
검은색 칸들이 정사각형 형태를 이루고 있고, 정사각형은 변이 4개이기 때문입니다.
문제 해결 접근 방법
이 문제의 핵심 아이디어는 격자 위의 교차점, 즉 서로 인접한 4개의 칸으로 이루어진 2×2 블록을 검사하는 것입니다.
어떤 교차점을 기준으로 네 칸 중 검은색 칸이 정확히 1개 또는 3개 존재한다면, 그 지점은 다각형의 꼭짓점(모서리)에 해당합니다. 모든 변이 가로·세로 방향으로 정렬된 직교 다각형에서는 꼭짓점의 개수와 변의 개수가 동일하므로, 그러한 지점의 개수를 모두 세면 곧 다각형의 변 개수를 구할 수 있습니다.
이를 절차적으로 정리하면 다음과 같습니다.
sides := 0
for initialize i := 1, when i < h, update (increase i by 1), do:
for initialize j := 1, when j < w, update (increase j by 1), do:
bl := 0
if grid[i - 1, j - 1] is same as '#', then:
(increase bl by 1)
if grid[i - 1, j] is same as '#', then:
(increase bl by 1)
if grid[i, j - 1] is same as '#', then:
(increase bl by 1)
if grid[i, j] is same as '#', then:
(increase bl by 1)
if bl is same as 1 or 3, then:
(increase sides by 1)
return sidesC++ 구현 예제
위 로직을 실제 C++ 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(int h, int w, vector<string> grid){
int sides = 0;
for(int i = 1; i < h; i++) {
for(int j = 1; j < w; j++) {
int bl = 0;
if(grid.at(i - 1).at(j - 1) == '#') {
bl++;
}
if(grid.at(i - 1).at(j) == '#') {
bl++;
}
if(grid.at(i).at(j - 1) == '#') {
bl++;
}
if(grid.at(i).at(j) == '#') {
bl++;
}
if(bl == 1 or bl == 3) {
sides++;
}
}
}
cout << sides;
}
int main() {
int h = 4, w = 4;
vector<string> grid = {"....", ".##.", ".##.", "...."};
solve(h, w, grid);
return 0;
}입력
4, 4, {"....", ".##.", ".##.", "...."}출력
4
코드의 시간 복잡도는 격자의 모든 칸을 한 번씩만 확인하므로 O(h × w)이며, 격자 크기가 커져도 효율적으로 동작합니다. 이처럼 2×2 블록 단위의 검사만으로 복잡한 기하 계산 없이 다각형의 변 개수를 간단하게 구할 수 있습니다.