BOJ 16234 : 인구 이동 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/16234

 

 

2차원 탐색은 보통 BFS를 이용한다.

2차원 MAP 탐색 기본 원리는 단지번호붙이기를 풀어보자.

 

단지번호붙이기와 다른 점은, queue에 담는 조건이 인접한 A[r][c]의 차이가 L 이상 R 이하인 경우로 바뀐 것이다.

어쨌든, 조건을 만족하는 경우 queue에 담으면서 영역을 확장해 나가면 된다.

 

그리고 선택된 영역을 visit으로 check해서 다음 BFS에 선택되지 않도록 한다.

 

먼저 r, c, visit배열에 대해 BFS로 영역을 만드는 하는 함수를 만들어보자.

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

int BFS(int r, int c, int visit[][MAX])
{
	int sum, cnt = 0;

	wp = rp = 0;

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

	visit[r][c] = 1;
	
	sum = A[r][c];
	cnt = 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 (nr < 0 || nc < 0 || nr > N - 1 || nc > N - 1) continue;
			
            /* 주변과 차이를 구하고 */
			int diff = abs(A[out.r][out.c] - A[nr][nc]);

			if (visit[nr][nc] == 0 && (L <= diff && diff <= R)) /* 조건 check */
			{
				queue[wp].r = nr; /* queue 의 push */
				queue[wp++].c = nc;

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

	for (int i = 0; i < wp; i++)
	{
		QUEUE rc = queue[i];
		A[rc.r][rc.c] = sum / cnt; /* 인구 이동 */
	}

	return cnt;
}

(r, c)는 선택하고 시작하므로, visit을 check하고 counting = 1로 시작한다.

그리고 선택된 영역의 총합과 영역의 수로 나눈 값으로 A[r][c]들을 변경해야하므로, sum으로 A값을 누적한다.

 

dr, dc 배열로 (r, c) 주변 4영역을 탐색한다. 

이때, 0을 넘어서거나 N이상인 곳은 탐색하면 안되므로 경계조건을 처리한다.

if (nr < 0 || nc < 0 || nr > N - 1 || nc > N - 1) continue;

경계조건 처리가 귀찮으면 주변의 벽을 매우 높게 잡아서 L이상 R이하가 되지 않도록 만들 수도 있다.

 

이제 queue를 이용해 국경선이 열리는 나라를 모두 얻었다.

이제 각 나라를 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)로 갱신해야한다.

 

총 연합의 인구수는 sum으로 갱신하였고, 칸의 개수는 cnt를 이용하여 구해두었다.

각 나라의 좌표는 queue에 저장되고 있었다. 더 정확히는 아직 저장되어있다.

BFS를 위해 queue를 모두 pop했지만, queue를 배열로 만들었으므로 i = 0 부터 wp까지 다시 훑어보기만 하면 된다.

for (int i = 0; i < wp; i++) 
{
	QUEUE rc = queue[i]; /* queue에 모두 저장되어 있다. */
	A[rc.r][rc.c] = sum / cnt;
}

pop연산은 rp(read pointer)로 인해 선입선출을 지키기 위한 index일 뿐,

실제로 queue에서 나라의 좌표가 사라진 것은 아니다.

 

이제 A[r][c]에 대해서 이동이 끝났다. 하지만 다른 영역에서도 국경선이 열려있을 수 있다.

따라서 모든 (r, c)에 대해 BFS를 실행해야 한다.

이때, 이동이 일어나지 않으면 BFS는 1 (cnt의 초깃값)을 return한다.

따라서 모든 (r, c)에 대해 1을 return하면 이동이 종료되었다고 판단할 수 있다.

int ALLBFS()
{
	int visit[MAX][MAX];

	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			visit[r][c] = 0; /* visit의 초기화 */

	int flag = 0;
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			if (visit[r][c] == 0) /* 방문하지 않은 곳이면 BFS 실행 */
			{
				int result = BFS(r, c, visit);
				if (result != 1) flag = 1; /* 모두 1을 return하면 flag = 0이 된다 */
			}
		}
	}
		
	return flag; 
}

int main(void)
{
	input();
	
	int ans = 0;

	while (1)
	{
		int result = ALLBFS(); /* 아무도 이동이 안일어난 경우 flag = 0 */
		if (result == 0) break;
		ans++;
	}

	printf("%d\n", ans);

	return 0;
}

 

while문을 이용해 계속해서 인구를 이동시키고, 모든 이동이 끝나면 종료하면 된다.

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (100 + 20)
#define abs(a) (((a) > 0) ? (a) : -(a))

int N, L, R;
int A[MAX][MAX];

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

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

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

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

void output()
{
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
			printf("%2d ", A[r][c]);
		putchar('\n');
	}
}

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

int BFS(int r, int c, int visit[][MAX])
{
	int sum, cnt = 0;

	wp = rp = 0;

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

	visit[r][c] = 1;
	
	sum = A[r][c];
	cnt = 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 (nr < 0 || nc < 0 || nr > N - 1 || nc > N - 1) continue;

			int diff = abs(A[out.r][out.c] - A[nr][nc]);

			if (visit[nr][nc] == 0 && (L <= diff && diff <= R))
			{
				queue[wp].r = nr; /* queue 의 push */
				queue[wp++].c = nc;

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

	for (int i = 0; i < wp; i++)
	{
		QUEUE rc = queue[i];
		A[rc.r][rc.c] = sum / cnt;
	}

	return cnt;
}

int ALLBFS()
{
	int visit[MAX][MAX];

	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			visit[r][c] = 0;

	int flag = 0;
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			if (visit[r][c] == 0)
			{
				int result = BFS(r, c, visit);
				if (result != 1) flag = 1;
			}
		}
	}
		
	return flag;
}

int main(void)
{
	input();
	
	int ans = 0;

	while (1)
	{
		int result = ALLBFS();
		if (result == 0) break;
		ans++;
	}

	printf("%d\n", ans);

	return 0;
}

실제 A형은 tc가 많으므로 ans를 0으로 매 tc마다 초기화하는 코드가 필요하다.