[코드트리] 냉방 시스템 (삼성 SW 역량테스트 2021 하반기 오전 2번)

삼성 A형 전체 링크

 

Codetree 기출문제 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/cooling-system

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

 

냉방 시스템 문제 풀이는 BOJ 23289 : 온풍기 안녕! 과 비슷하지만,

입력값, 격자의 크기, 벽 설치 위치, 방향의 정의가 다르다.

 

온풍기 안녕은 R x C 지만, 냉방 시스템은 N x N이므로, 입력값 처리를 다르게 해야 한다.

 

그리고 s가 1인 경우, 왼쪽에 벽을 설치한다. (온풍기 안녕은 오른쪽)

	for (int i = 0; i < M; i++)
	{
		int r, c, s;

		scanf("%d %d %d", &r, &c, &s);

		if (s == 1)
		{
			wall[r][c].direction[LEFT] = 1;
			wall[r][c - 1].direction[RIGHT] = 1;
		}
		else
		{
			wall[r][c].direction[UP] = 1;
			wall[r - 1][c].direction[DOWN] = 1;
		}
	}

 

방향의 정의가 다르기 때문에 코드를 수정하였다.

#define LEFT (2)
#define UP (3)
#define RIGHT (4)
#define DOWN (5)

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

 

따라서 controlTemperature에서도 dir는 2 ~ 5로 처리해야 한다.

	for (int dir = 2; dir <= 5; dir++)
	{
		int nr, nc;

		nr = r + dr[dir];
		nc = c + dc[dir];

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

		if (wall[r][c].direction[dir] == 1) continue;

		if (MAP[r][c] > MAP[nr][nc]) // 온도가 높은 경우만 확산
		{
			int diff = (MAP[r][c] - MAP[nr][nc]) / 4;

			save -= diff;
			tmpMAP[nr][nc] += diff;
		}
	}

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (20 + 10)

#define LEFT (2)
#define UP (3)
#define RIGHT (4)
#define DOWN (5)

int T;
int N, M, K;
int A[MAX][MAX];
int MAP[MAX][MAX];

typedef struct st1
{
	int r;
	int c;
}RC;

RC checkPoint[MAX * MAX];
int ccnt;

typedef struct st2
{
	int r;
	int c;
	int dir;
}COOLER;

COOLER cooler[MAX * MAX];
int coolCnt;

typedef struct st3
{
	int r;
	int c;
	int temp;
}QUEUE;

typedef struct st4
{
	int direction[6];
}WALL;

WALL wall[MAX][MAX];

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

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

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

			if (A[r][c] == 1)
			{
				checkPoint[ccnt].r = r;
				checkPoint[ccnt++].c = c;
			}
			else if (A[r][c] != 0)
			{
				cooler[coolCnt].r = r;
				cooler[coolCnt].c = c;
				cooler[coolCnt++].dir = A[r][c];
			}
		}
	}

	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			for (int d = 2; d <= 5; d++)
				wall[r][c].direction[d] = 0;

	for (int i = 0; i < M; i++)
	{
		int r, c, s;

		scanf("%d %d %d", &r, &c, &s);

		if (s == 1)
		{
			wall[r][c].direction[LEFT] = 1;
			wall[r][c - 1].direction[RIGHT] = 1;
		}
		else
		{
			wall[r][c].direction[UP] = 1;
			wall[r - 1][c].direction[DOWN] = 1;
		}
	}
}

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

void heat(int r, int c, int dir)
{
	QUEUE queue[MAX * MAX];
	int visit[MAX][MAX] = { 0 };
	int wp, rp;
	int sr, sc, temp;

	temp = 5;
	sr = r, sc = c;

	wp = rp = 0;

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

	visit[r][c] = 1;

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

		if (out.temp == 0) break;

		if (out.r <= 0 || out.c <= 0 || out.r > N || out.c > N) continue;

		MAP[out.r][out.c] += out.temp;

		if (dir == RIGHT || dir == LEFT)
		{
			int nr, nc;

			nc = out.c + dc[dir];

			// ↖ ↗ 위
			nr = out.r - 1;
			if (visit[nr][nc] == 0 // queue에 들어가지 않은 장소에서
				// (x, y)와 (x - 1, y) 사이에 벽이 없어야 한다.
				&& (wall[out.r][out.c].direction[UP] == 0)
				// (x - 1,y)와 (x - 1, y + dc[dir]) 사이에 벽이 없어야 한다.
				&& (wall[nr][out.c].direction[dir] == 0))
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].temp = out.temp - 1;

				visit[nr][nc] = 1;
			}


			// ← → 옆
			nr = out.r;
			if (visit[nr][nc] == 0 // queue에 들어가지 않은 장소에서
				// (x, y)와 (x, y + dc[dir]) 사이에 벽이 없어야 한다.
				&& (wall[out.r][out.c].direction[dir] == 0))
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].temp = out.temp - 1;

				visit[nr][nc] = 1;
			}

			// ↙ ↘ 아래
			nr = out.r + 1;
			if (visit[nr][nc] == 0 // queue에 들어가지 않은 장소에서
				// (x, y)와 (x + 1, y) 사이에 벽이 없어야 한다.
				&& (wall[out.r][out.c].direction[DOWN] == 0)
				// (x + 1,y)와 (x + 1, y + dc[dir]) 사이에 벽이 없어야 한다.
				&& (wall[nr][out.c].direction[dir] == 0))
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].temp = out.temp - 1;

				visit[nr][nc] = 1;
			}
		}
		else // UP, DOWN
		{
			int nr, nc;

			nr = out.r + dr[dir];

			// ↖ ↙ 왼
			nc = out.c - 1;
			if (visit[nr][nc] == 0 // queue에 들어가지 않은 장소에서
				// (x, y)와 (x, y - 1) 사이에 벽이 없어야 한다.
				&& (wall[out.r][out.c].direction[LEFT] == 0)
				// (x,y - 1)와 (x + dr[dir], y - 1) 사이에 벽이 없어야 한다.
				&& (wall[out.r][nc].direction[dir] == 0))
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].temp = out.temp - 1;

				visit[nr][nc] = 1;
			}


			// ↑ ↓ 위, 아래
			nc = out.c;
			if (visit[nr][nc] == 0 // queue에 들어가지 않은 장소에서
				// (x, y)와 (x + dr[dir], y) 사이에 벽이 없어야 한다.
				&& (wall[out.r][out.c].direction[dir] == 0))
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].temp = out.temp - 1;

				visit[nr][nc] = 1;
			}

			// ↗ ↘
			nc = out.c + 1;
			if (visit[nr][nc] == 0 // queue에 들어가지 않은 장소에서
				// (x, y)와 (x, y + 1) 사이에 벽이 없어야 한다.
				&& (wall[out.r][out.c].direction[RIGHT] == 0)
				// (x,y + 1)와 (x + dr[dir], y + 1) 사이에 벽이 없어야 한다.
				&& (wall[out.r][nc].direction[dir] == 0))
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].temp = out.temp - 1;

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

void controlTemperature()
{
	int tmpMAP[MAX][MAX] = { 0 };

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] > 0)
			{
				int save = MAP[r][c];

				for (int dir = 2; dir <= 5; dir++)
				{
					int nr, nc;

					nr = r + dr[dir];
					nc = c + dc[dir];

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

					if (wall[r][c].direction[dir] == 1) continue;

					if (MAP[r][c] > MAP[nr][nc]) // 온도가 높은 경우만 확산
					{
						int diff = (MAP[r][c] - MAP[nr][nc]) / 4;

						save -= diff;
						tmpMAP[nr][nc] += diff;
					}
				}

				tmpMAP[r][c] += save;
			}
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			MAP[r][c] = tmpMAP[r][c];
}

void decreaseTemperature()
{
	if (MAP[1][1]) MAP[1][1]--;
	if (MAP[N][1]) MAP[N][1]--;
	if (MAP[1][N]) MAP[1][N]--;
	if (MAP[N][N]) MAP[N][N]--;

	for (int r = 2; r <= N - 1; r++)
		if (MAP[r][1]) MAP[r][1]--;

	for (int r = 2; r <= N - 1; r++)
		if (MAP[r][N]) MAP[r][N]--;

	for (int c = 2; c <= N - 1; c++)
		if (MAP[1][c]) MAP[1][c]--;

	for (int c = 2; c <= N - 1; c++)
		if (MAP[N][c]) MAP[N][c]--;
}

int testCheckPoint()
{
	for (int i = 0; i < ccnt; i++)
		if (MAP[checkPoint[i].r][checkPoint[i].c] < K) return 0;

	return 1;
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		int timer = 0;
		while (1)
		{
			for (int i = 0; i < coolCnt; i++)
			{
				int r, c, dir;

				r = cooler[i].r;
				c = cooler[i].c;
				dir = cooler[i].dir;

				heat(r + dr[dir], c + dc[dir], dir);
			}

			controlTemperature();

			decreaseTemperature();

			timer++;

			if (testCheckPoint()) break;
			if (timer > 100) break;
		}

		if (timer == 101) printf("-1\n");
		else printf("%d\n", timer);
	}

	return 0;
}