BOJ 2667 : 단지번호붙이기

알고리즘 문제 전체 링크
 
www.acmicpc.net/problem/2667
 

이후 설명 및 입/출력은 링크 참고

2차원 배열의 구역을 BFS, queue를 이용해 나눠보자.
집인 곳을 발견하면, 집 주변의 영역을 찾아야 한다.
 
BFS를 이용해 푸는 방법은 다음과 같다.
 
1) 집이 아니면(0) 넘어간다. 
2) (r, c)가 집이면 queue에 담고 visit[r][c] = 1 로 체크한다. (다음에 다시 담지 않게 하기 위해)
3) (r, c)의 4방향이 집이고 visit이 0이면 queue에 담는다.  이때, queue에 담으면서 집의 개수(영역의 크기)를 센다.
4) 최종 영역의 개수를 return 한다.
5) 2) ~ 3)을 queue가 빌 때까지 한다.
 
※ BFS 탐색 과정은 유니티를 이용해서 확인할 수 있다.
 
실제로 그림으로 확인해보자.
먼저, MAP의 경우 (1, 1)부터 입력을 받는다.
그렇게 하면, MAP의 주변은 자동으로 0이기 때문에 경계 조건을 체크하지 않아도 된다.

void input()
{
	scanf("%d", &N);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N;c++)
			scanf("%1d", &MAP[r][c]);
}

이제 BFS를 시작해보자.

for (int r = 1; r <= N; r++)
	for (int c = 1; c <= N; c++)
		if (MAP[r][c] == 1 && visit[r][c] == 0) ANS[ans++] = BFS(r, c);

모든 MAP을 돌면서, 집이 있는 경우, 그리고 이전 BFS에 의해 방문하지 않은 곳이면 BFS를 시작해서 영역을 센다.
각 영역의 개수를 저장해서 출력해야 하므로 ANS 배열에 저장한다.
 
이제 BFS 코드를 보자. 4방향 탐색을 위해 배열 dr, dc를 선언해둔다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

int BFS(int r, int c)
{
	int cnt;

	wp = rp = 0;

	cnt = 1; /* 첫 영역을 세야하므로 1로 시작 */

	queue[wp].r = r; /* 시작 좌표 queue에 push */
	queue[wp++].c = c;

	visit[r][c] = 1; /* 시작 좌표 check */

	while (wp > rp)
	{
		...
	}

	return cnt;
}

queue의 wp와 rp를 초기화하고, 집인 영역부터 시작하므로 개수는 1로 초기화 한다. 
그리고 현재 영역도 다시 방문하지 못하도록 visit[r][c] = 1로 체크한다.
 
그림의 예시대로 하면 MAP[1][1] = 0이므로 넘어가게 되고, MAP[1][2]부터 BFS가 실행된다.

이제 queue가 빌 때까지, 2) ~ 3)을 계속 반복하면 된다.
먼저 queue에서 1개를 꺼낸다.

	while (wp > rp)
	{
		QUEUE out = queue[rp++];
        ...
	}

 
그리고 dr, dc 배열을 이용해 4방향을 check 한다.

	while (wp > rp)
	{
		QUEUE out = queue[rp++]; /* queue의 pop */

		for (int i = 0; i < 4;i++) /* dr, dc 배열을 이용해 현재 좌표의 4방향 탐색 */
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && MAP[nr][nc] == 1)
			{
				queue[wp].r = nr; /* queue 의 push */
				queue[wp++].c = nc;

				visit[nr][nc] = 1;
				cnt++;
			}
		}
	}

 
(1, 2)를 기준으로 visit이 0이고, MAP이 1인 곳은 오른쪽과 아래다. 
따라서 아래와 같은 그림이 된다.
queue가 아직 비어있지 않으므로, 다시 (1, 3)을 꺼내서 4방향을 탐색한다.

brown 색이 현재 pop된 좌표이다.

이때, (1, 2)는 visit에 의해 담기지 않게 되고, (1, 4)와 (0, 3)은 MAP이 0이기 때문에 queue에 담기지 않는다.

 
계속해서 queue가 빌 때 까지, 탐색해보면 아래의 그림과 같이 된다.
 
(2, 2) pop

 
(2, 3) pop

(3, 2) pop

(3, 3) pop → (3, 3) 주변 4방향은 visit이 1이거나 MAP이 0이므로 종료.
(3, 1) pop → (3, 1) 주변 4방향은 visit이 1이거나 MAP이 0이므로 종료.
 
따라서 최종 visit 표시는 아래와 같이 되고, BFS는 queue에 담긴 횟수인 총 7을 return하게 된다.

 
다시 BFS 실행 코드를 보면, MAP이 1이지만 visit에 의해 한번 방문한 영역은 방문하지 않게 되고, 
옆의 영역을 다시 counting 하게 된다.

for (int r = 1; r <= N; r++)
	for (int c = 1; c <= N; c++)
		if (MAP[r][c] == 1 && visit[r][c] == 0) ANS[ans++] = BFS(r, c);

그리고 ANS에는 각 영역의 개수가 담겨있고, 영역의 수는 ans로 센다.
마지막으로, 적절히 정렬해서 출력만 해주면 된다.
 
최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (25 + 5)

int N;
int MAP[MAX][MAX];
int visit[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}QUEUE;

QUEUE queue[MAX*MAX];
int wp, rp;

int ANS[MAX*MAX];

void input()
{
	scanf("%d", &N);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N;c++)
			scanf("%1d", &MAP[r][c]);
}

int dr[] = { 0,-1,0,1 };
int dc[] = { -1,0,1,0 };

int BFS(int r, int c)
{
	int cnt;

	wp = rp = 0;

	cnt = 1;

	queue[wp].r = r;
	queue[wp++].c = c;

	visit[r][c] = 1;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		for (int i = 0; i < 4;i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && MAP[nr][nc] == 1)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;
				cnt++;
			}
		}
	}

	return cnt;
}

int main(void)
{
	int ans;

	input();

	ans = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (MAP[r][c] == 1 && visit[r][c] == 0) ANS[ans++] = BFS(r, c);
	
	printf("%d\n", ans);

	/* 출력을 위한 정렬 */
	for (int i = 0; i < ans - 1; i++)
	{
		for (int k = i + 1; k < ans; k++)
		{
			if (ANS[i] > ANS[k])
			{
				int tmp = ANS[i];
				ANS[i] = ANS[k];
				ANS[k] = tmp;
			}
		}
	}

	for (int i = 0; i < ans; i++) printf("%d\n", ANS[i]);

	return 0;
}