[C++] 백준 2576번:색종이-2

문제링크

1380번: 귀걸이

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다.

입력

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다. 

출력

첫째 줄에 색종이가 붙은 검은 영역의 둘레의 길이를 출력한다.

 

풀이

도화지에서 색종이로 덮힌 공간을 1로 체크해준다고 하면 1에서 0으로 변하는 곳이 둘레가 된다.

따라서 모든 칸에 대해 해당 칸이 1이라면 상하좌우를 확인하고 0인 칸의 개수를 세어주면 된다.

 

코드

#include <iostream>
using namespace std;
bool arr[101][101];// 도화지
int n, x, y, cnt;
 
// 상하좌우 확인용
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
 
        for (int a = x; a < x + 10; a++) {
            for (int b = y; b < y + 10; b++) {
                arr[a][b] = true;
            }
        }
    }
 
    for (int a = 0; a < 100; a++) {
        for (int b = 0; b < 100; b++) {
            if (arr[a][b] == true) {
                // 상하좌우 확인
                for (int c = 0; c < 4; c++) {
                    if (arr[a + dx[c]][b + dy[c]] == false) {
                        cnt++;
                    }
                }
            }
        }
    }
 
    cout << cnt;
 
}

 

메모

풀이를 떠올린 것은 오래 걸리지 않았는데 구현 하는데 애를 먹었다.

배열로 미리 만들어두는 것은 굉장히 좋은 방법인 것 같다.