BOJ 23289 : 온풍기 안녕! (삼성 SW TEST A형)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

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

https://www.acmicpc.net/problem/23289

좌표에 맞춰서 상하좌우 define과 dr, dc 배열을 정의한다.

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

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

문제를 풀기 위한 구조체를 정의한다.

RC = 온도를 체크해야하는 checkPoint의 좌표 (r, c)

HEATER = 온풍기의 좌표 및 방향 관리

QUEUE = 바람을 불 때 사용할 큐

WALL = 벽을 체크하기 위한 구조체

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

RC checkPoint[MAX * MAX];
int ccnt;

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

HEATER heater[MAX * MAX];
int hcnt;

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

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

WALL wall[MAX][MAX];

R, C, K를 받은 후, 온도를 체크할 좌표와 온풍기를 입력받는다.

이후 벽의 좌표를 입력받으면 wall[r][c]와 주변 벽도 체크한다.

예를 들어 t == 1이란 것은 (r, c)에서 오른쪽에 벽이 있고, (r, c + 1)에서는 왼쪽에 벽이 있게 된다.

따라서 아래와 같이 표현 가능하다.

wall[r][c].direction[RIGHT] = 1;
wall[r][c + 1].direction[LEFT] = 1;

input은 아래와 같이 구현된다.

void input()
{
	scanf("%d %d %d", &R, &C, &K);

	for (int r = 1; r <= R; r++)
	{
		for (int c = 1; c <= C; c++)
		{
			scanf("%d", &A[r][c]);

			if (A[r][c] == 5)
			{
				checkPoint[ccnt].r = r;
				checkPoint[ccnt++].c = c;
			}
			else if (A[r][c] != 0)
			{
				heater[hcnt].r = r;
				heater[hcnt].c = c;
				heater[hcnt++].dir = A[r][c];
			}
		}
	}

	scanf("%d", &W);

	for (int i = 0; i < W; i++)
	{
		int r, c, t;

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

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

main은 문제에서 제시한 순서대로 구현한다.

1. for 문, heat() - 모든 온풍기에서 바람이 한 번 나옴

2. controlTemperature() - 온도가 조절됨

3. decreaseTemperature() - 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소

4. chocolate++ - 초콜릿을 하나 먹는다.

5. if (testCheckPoint()) break; - 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사.

int main(void)
{
	input();

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

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

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

		controlTemperature();

		decreaseTemperature();

		chocolate++;

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

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

	return 0;
}

1. for 문, heat() - 모든 온풍기에서 바람이 한 번 나옴

단순히 for문을 이용해서 바람을 불게하면, 벽 check 여부로 구현이 까다롭다.

따라서 큐를 이용해 (r, c)와 direction을 기준으로 세 방향을 검사한 후에, queue에 담는다.

queue에 담을 때는 온도가 1씩 감소하며, 온도가 0이 되는 경우에는 종료해도 된다.

queue에서 나올 때, MAP[r][c]에 온도를 누적한다.

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 > R || out.c > C) 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;
			}
		}
	}
}

wall[r][c]와 주변 좌표에 벽을 표시하였으므로, 문제에서 제시한 대로 방향을 잘 고려하여 벽 체크를 하면 된다.

2. controlTemperature() - 온도가 조절됨

미세먼지 안녕!의 diffusion() 함수와 비슷한 로직이다.

동시에 발생해야 하기 때문에 임시 MAP을 만들어서 퍼뜨린다.

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

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

				for (int dir = 1; dir <= 4; dir++)
				{
					int nr, nc;

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

					if (nr <= 0 || nc <= 0 || nr > R || nc > C) 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 <= R; r++)
		for (int c = 1; c <= C; c++)
			MAP[r][c] = tmpMAP[r][c];
}

3. decreaseTemperature() - 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소

모서리와 꼭짓점이 중복되지 않게 따로 구현하였다.

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

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

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

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

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

4. chocolate++ - 초콜릿을 하나 먹는다.

5. if (testCheckPoint()) break; - 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사.

input에서 checkPoint를 따로 모아두었다.

모든 좌표를 검사하면 된다.

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

	return 1;
}

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (20 + 10)

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

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

int R, C, K, W;
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;
}HEATER;

HEATER heater[MAX * MAX];
int hcnt;

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

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

WALL wall[MAX][MAX];

void input()
{
	scanf("%d %d %d", &R, &C, &K);

	for (int r = 1; r <= R; r++)
	{
		for (int c = 1; c <= C; c++)
		{
			scanf("%d", &A[r][c]);

			if (A[r][c] == 5)
			{
				checkPoint[ccnt].r = r;
				checkPoint[ccnt++].c = c;
			}
			else if (A[r][c] != 0)
			{
				heater[hcnt].r = r;
				heater[hcnt].c = c;
				heater[hcnt++].dir = A[r][c];
			}
		}
	}

	scanf("%d", &W);

	for (int i = 0; i < W; i++)
	{
		int r, c, t;

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

		if (t == 1)
		{
			wall[r][c].direction[RIGHT] = 1;
			wall[r][c + 1].direction[LEFT] = 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 <= R; r++)
	{
		for (int c = 1; c <= C; 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 > R || out.c > C) 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 <= R; r++)
	{
		for (int c = 1; c <= C; c++)
		{
			if (MAP[r][c] > 0)
			{
				int save = MAP[r][c];

				for (int dir = 1; dir <= 4; dir++)
				{
					int nr, nc;

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

					if (nr <= 0 || nc <= 0 || nr > R || nc > C) 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 <= R; r++)
		for (int c = 1; c <= C; c++)
			MAP[r][c] = tmpMAP[r][c];
}

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

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

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

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

	for (int c = 2; c <= C - 1; c++)
		if (MAP[R][c]) MAP[R][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)
{
	input();

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

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

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

		controlTemperature();

		decreaseTemperature();

		chocolate++;

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

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

	return 0;
}

실제 A형에서는 wall과 MAP을 초기화하는 코드가 필요하다.

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

BOJ 23291 : 어항 정리 (삼성 SW TEST A형) (2)	2021.11.06
BOJ 23290 : 마법사 상어와 복제 (삼성 SW TEST A형) (0)	2021.11.06
BOJ 23288 : 주사위 굴리기 2 (삼성 SW TEST A형) (0)	2021.10.25
BOJ 21611 : 마법사 상어와 블리자드 (삼성 SW TEST A형) (0)	2021.05.01
BOJ 21610 : 마법사 상어와 비바라기 (삼성 SW TEST A형) (0)	2021.04.30

피로물든딸기의 라이브러리

BOJ 23289 : 온풍기 안녕! (삼성 SW TEST A형)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

댓글

티스토리툴바

BOJ 23289 : 온풍기 안녕! (삼성 SW TEST A형)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

관련글

댓글

티스토리툴바