[코드트리] 토스트 계란틀 (삼성 SW 역량테스트 2018 하반기 오전 2번)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/toast-eggmold

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

 

토스트 계란틀 문제 풀이는 BOJ 16234 : 인구 이동과 같다.

#include <stdio.h>

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

int T;
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)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		int ans = 0;

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

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

	return 0;
}