USACO: 둘레(Bronze)

문제

농부 존은 그의 들판에 N(1≤N≤10,000)개의 건초 더미를 놓으려 한다. 들판은 1*1 크기의 사각형으로 구성된 100*100 크기이고, 건초 더미들은 각각 1*1 크기의 사각형 한 칸을 차지한다. (한 칸에 두 개의 건초 더미가 놓이는 일은 없다)

농부 존은 건초 더미로 연결된 다양한 형태의 하나의 큰 영역이 생기는 것을 알았다. 즉, 건초 더미들 모두 인접한 (동서남북으로 한 칸) 곳에 다른 건초 더미가 있다. 한 건초 더미에서 출발해서 다른 모든 건초 더미에 도달할 수 있다. 건초 더미로 연결된 영역은 “구멍”을 포함할수있다. 구멍은 건초 더미로 완전히 둘러싸인 빈 영역이다. 농부 존이 건초 베일에 의해 형성되는 영역의 둘레를 계산하는 것을 도와주시오. “구멍”은 둘레에 영향을 주지 않는다.

 

입력 

첫 번째 줄에 건초 더미의 수 N이 입력된다. (1≤N≤10,000) 두 번째 줄부터 N줄에 걸쳐 건초 더미가 놓인 곳의 위치 X(가로), Y(세로)가 공백으로 구분되어 입력된다. X, Y 모두 정수이고 1이상 100이하이다.

 

출력

건초 더미로 연결된 영역의 둘레의 길이를 출력하라.

 

입력
8
5 3
5 4
8 4
5 5
6 3
7 3
7 4
6 5

출력
14

 

아래 문제와 같은 문제이다!

USACO

 

풀이

'건초 더미 밖 빈칸'을 기준으로 확산하면서, 맞닿은 건초의 개수를 세어주면, 건초더미의 둘레가 된다.

#include<iostream>
#define MAX 102
using namespace std;

int N, r, c;
bool hay[MAX][MAX];
bool visited[MAX][MAX];
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};

void input(){
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> r >> c;
        hay[r][c] = true; // 건초
    }
}

int dfs(int y, int x){ // '건초 더미 밖 빈칸'을 기준으로 확산
    int res = 0;
    visited[y][x] = true;
    for(int d=0; d<4; d++){
        int ny = y+dy[d];
        int nx = x+dx[d];
        if(ny<0 || ny>=MAX || nx<0 || nx>=MAX) continue;
        if(hay[ny][nx]) res++;
        if(hay[ny][nx] || visited[ny][nx]) continue;
        res += dfs(ny, nx);
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    cout << dfs(0, 0);
}