[Algorithm][DFS][USACO] 2013Feb. 둘레

순서

I. 문제

II. 접근

III. 구현

문제출처 : www.usaco.org/index.php?page=viewproblem2&cpid=243

---

I. 문제

농부 존이 들판에 N개(1 이상 10000 이하) 개의 건초더미를 놓는다.
구성된 들판은 100*100크기이고, 건초더미들은 각각 1*1 크기를 갖는다.
존은 건초 더미로 연결된 다양한 형태의 하나의 큰 영역이 생기는 것을 알았고
건초더미들은 모두 인접한(동서남북) 곳에 다른 건초 더미가 있다.
건초 더미로 연결된 영역은 "구멍"이 있다. 구멍은 건초더미로 완전히 둘러싸인 빈 영역이다.
농부 존이 건초 베일에 의해 형성되는 영역의 둘레를 계산하시오. (구멍의 영향은 받지 않는다.)

>>요약 : 건초를 둘건데, 모두 인접하게 있고 그 건초의 둘레는?? (구멍 무시하고 겉에만)

입력형식 첫번 째 줄에 건초 더미의 수 N이 입력된다.(1<=N<=10000) 두번 째 줄 부터 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

 

---

II. 접근 (DFS - Flood Fill)

사실 이런 둘레의 길이를 재는 문제는 굉장히 다양한 문제가 있다.
유명한 "색종이" 문제부터...

이번 문제는 사이에 생긴 구멍을 무시하고 둘레만 구하는 문제이기 때문에 굉장히 쉽다.

빨간선의 길이가 답

DFS로 구현된 "Flood Fill" 을 이용하자

이런 둘레 구하기 문제는 건초를 중심으로 보면 안되고,
주변을 중점적으로 봐야한다.

어떤 모양이 나와도 둘레를 구할 수 있는 확실한 방법은
바깥 배열에서 4방향을 확인했을 때 건초가 있을 때 +1 해주는 것이다.

따라서 배열의 빈 부분을 DFS로 확산하면서 4방향을 탐색해준다.
건초가 있다면 +1(변1개추가) 비어있다면 확산을 반복해준다.

주변 배열에서 체크해주는 값

만약 구멍의 둘레도 포함시켜야 한다면,
반복문으로 배열의 빈 부분을 찾을 때 DFS로 추가해주면 된다!!

혹시나,, 그냥 각 변마다 (최대-최소+1) *2 하면 될 것이라고 생각한다면...
凹와 같은 모양의 반례가 있음을 생각하자.

 

III. 구현

<hide/>
#include <stdio.h>
#include <iostream>
#include <cstring.h>

using namespace std;

int N;
int map[100 + 10][100 + 10];
int sol{ 0 };

void input() {
	cin >> N;
	int tempx;
	int tempy;
	for (int i = 0; i < N; i++) {
		cin >> tempx >> tempy;
		map[tempy][tempx] = 1;
	}
}

void floodFill(int i, int j) {

	int dx[4] = { 0,0,-1,1 };
	int dy[4] = { 1,-1,0,0 };
    
    // 건초를 발견하면 갯수 +1 해주고 돌아감.
	if (map[i][j] == 1) {
		sol++;
		return;
	}
    
    // 방문 안하고, 비어있는 0일 때
	else if (map[i][j] == 0) {

		//4방향 반복
		for (int ii = 0; ii < 4; ii++) {
        
            //밖으로 나갔을 때 무시
			if (((i + dy[ii]) == -1) or (i + dy[ii] == 102)
				or (j + dx[ii] == -1) or (j + dx[ii] == 102)) continue;

            // 0일 때 확산 해야 하므로, 방문표시는 다른 숫자인 2로 해준다.
			map[i][j] = 2;
            
            //들렀다는 방문 표시 후 추가 확산
			floodFill(i + dy[ii], j + dx[ii]);
		}
	}

}

int main() {
	input();
    memset(map,0,sizeof(map));

    // 0,0은 무조건 빈 부분이므로 여기서부터 시작
	floodFill(0, 0);

	cout << sol;

	return 0;
}