알고리즘/[ADV] 삼성 SW 역량 테스트 A형
[코드트리] 냉방 시스템 (삼성 SW 역량테스트 2021 하반기 오전 2번)
피로물든딸기
2024. 6. 9. 00:57
반응형
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;
}반응형