[백준] 색종이 - 2

https://www.acmicpc.net/problem/2567

2567번: 색종이 - 2

구현 문제입니다.

 

우선 문제부터 간단하게 설명해보면, 100x100의 하얀 도화지 위에 검정 종이들을 붙입니다. 이 때, 검은 영역의 둘레 길이를 출력해야 합니다.

 

<Solution>

저의 구현의 경우 하얀 부분을 쭉 채워나가면서, 검정 경계선을 만났을 때 카운팅을 하는 방식을 사용하였습니다. 

 

흔히 flood fill 이라 불리는 풀이방식을 사용하였습니다. 내부의 둘레도 둘레에 포함시켜야 하므로 for loop로 grid 전체를 스캔하였고, 방문한 곳은 마킹을 해서 최대한 중복을 피했습니다. 

 

하지만 이 문제의 경우, 더 간단하게 해결이 가능합니다. 총 3가지 정도의 방식을 생각해 볼 수 있는데

 

1. row 방향으로 한칸씩 옆으로 건너가며 색이 변화하는 지점에서 count를 올린다. 이 방식을 column방향에 대해서도 반복한다.  2. Flood fill, BFS등의 알고리즘을 사용한다. 3. 검정 부분에서 상하좌우를 탐색해서 흰색인 것의 갯수를 카운팅 한다.

이중에서 3번이 그래도 제일 편할 것 같다는 생각이 듭니다.

 

1번 방식을 이용한 구현 코드는 아래와 같습니다. 

#include <iostream>
using namespace std;
 
int N;
int A[100+10];
int B[100+10];
void InputData(){
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> A[i] >> B[i];
    }
}
 
char grid[110][110];
 
void fill_grid(int r, int c){
    for(int i = 0; i<10; i++){
        for(int j = 0; j<10; j++){
            grid[r+i][c+j] = '1';
        }
    }
}
int d_row[] = {0, 0, 1, -1};
int d_col[] = {1, -1, 0, 0};
int cnt = 0;
void ff(int r, int c){
     
    if(r<0 || c<0 || r>101 || c>101) return;
    if(grid[r][c] == '2') return;
 
    if(grid[r][c] == '1'){
         
        cnt++;
        return;
    }
 
    grid[r][c] = '2';
    for(int i = 0; i<4; i++){
        ff(r+d_row[i], c+d_col[i]);
    }
    return;
 
 
 
}
void sol(){
    for(int i = 0; i<N; i++){
        fill_grid(A[i]+1, B[i]+1);
 
 
    }
    // flood fill
     
    for(int i =0; i<=101; i++){
        for(int j = 0; j<= 101; j++){
            if(grid[i][j] != '1')
            ff(i,j);
        }
    }
 
}
 
int main(){
    int ans = -1;
 
    InputData();// 입력받는 부분
 
    // 여기서부터 작성
    sol();
 
    cout << cnt << endl;// 출력하는 부분
    return 0;
}