[코드트리] AI 로봇청소기 (삼성 SW 역량테스트 2025 하반기 오후 1번)

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

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/ai-robot/description

참고

- 코드트리 빵 (삼성 SW 역량테스트 2022 하반기 오후 1번)

좌표를 관리하기 위한 RC 구조체와 문제에서 제시하는 값을 define한다.

#define MAX (30 + 5)
#define WALL (-1)
#define INF (0x7fff0000)

#define RIGHT (0)
#define BOTTOM (1)
#define LEFT (2)
#define UP (3)

int T;
int N, K, L;

int MAP[MAX][MAX];
bool check[MAX][MAX]; // 청소기 좌표

struct RC
{
	int r;
	int c;
};

RC cleaner[50 + 5];
RC queue[MAX * MAX];

// →, ↓, ←, ↑
int dr[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };

MAP 주변은 벽(-1)으로 처리한다.

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

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = WALL;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);

	for (int k = 1; k <= K; k++)
	{
		int r, c;

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

		cleaner[k].r = r;
		cleaner[k].c = c;
	}
}

다음과 같이 시뮬레이션한다.

0. 현재 청소기 좌표 처리

1. 청소기 이동

2. 청소

3. 먼지 축적

4. 먼지 확산

5. 전체 먼지 출력

void simulate()
{
	for (int l = 0; l < L; l++)
	{
		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= N; c++)
				check[r][c] = 0; // 청소기 좌표 초기화

		// 0. 현재 청소기 좌표 체크
		for (int k = 1; k <= K; k++)
			check[cleaner[k].r][cleaner[k].c] = true;

		// 1. 청소기 이동
		for (int k = 1; k <= K; k++)
		{
			RC rc = getDustRC(k);

			check[cleaner[k].r][cleaner[k].c] = false;

			cleaner[k].r = rc.r;
			cleaner[k].c = rc.c;

			check[cleaner[k].r][cleaner[k].c] = true;
		}

		// 2. 청소
		for (int k = 1; k <= K; k++) clean(k);

		// 3. 먼지 축적
		addDust();

		// 4. 먼지 확산
		spreadDust();

		// 5. 출력
		printf("%d\n", getDust());		
	}
}

0. 현재 청소기 좌표 처리

다른 청소기를 지나갈 수 없으므로, check 배열로 현재 청소기 좌표를 표시해둔다.

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			check[r][c] = 0; // 청소기 좌표 초기화

	// 0. 현재 청소기 좌표 체크
	for (int k = 1; k <= K; k++)
		check[cleaner[k].r][cleaner[k].c] = true;

1. 청소기 이동

코드트리 빵을 참고하여 가장 가까운 오염된 격자를 찾는다.

여러 개일 경우 행 번호가 작고, 행 번호가 같으면 열 번호가 작은 격자를 찾는다.

이동 가능한 격자가 없는 청소기는 현재 자리를 유지하도록 처리한다.

RC getDustRC(int index) // BFS
{
	RC ret;
	int rp, wp;
	int visit[MAX][MAX] = { 0 };

	rp = wp = 0;
	int sr = cleaner[index].r;
	int sc = cleaner[index].c;

	if (MAP[sr][sc] > 0) return { sr, sc };
	queue[wp].r = sr;
	queue[wp++].c = sc;

	visit[sr][sc] = 1;
	ret.r = ret.c = INF;
	int minDistance = INF;
	while (rp < wp)
	{
		RC out = queue[rp++];

		// 먼지를 찾은 경우 + 다른 청소기가 위치하지 않은 경우
		if (MAP[out.r][out.c] > 0 && check[out.r][out.c] == false)
		{
			if (visit[out.r][out.c] < minDistance)
			{
				minDistance = visit[out.r][out.c];
				ret = out;
			}
			else if (visit[out.r][out.c] == minDistance)
			{
				if (out.r < ret.r) ret = out;
				else if (out.r == ret.r)
				{
					if (out.c < ret.c)
						ret = out;
				}
			}

			continue;
		}

		for (int i = 0; i < 4; i++)
		{
			int nr, nc;

			nr = out.r + dr[i];
			nc = out.c + dc[i];

			if (MAP[nr][nc] == WALL || check[nr][nc] == true) continue;
			if (visit[nr][nc] != 0) continue;

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

			visit[nr][nc] = visit[out.r][out.c] + 1;
		}
	}

	if (ret.r == INF) return { sr, sc };

	return ret;
}

BFS(getDustRC)를 이용하여 좌표를 찾았다면 check를 갱신한다.

	// 1. 청소기 이동
	for (int k = 1; k <= K; k++)
	{
		RC rc = getDustRC(k);

		check[cleaner[k].r][cleaner[k].c] = false;

		cleaner[k].r = rc.r;
		cleaner[k].c = rc.c;

		check[cleaner[k].r][cleaner[k].c] = true;
	}

2. 청소

선택된 청소기에 대해 청소를 가장 많이 할 수 있는 방향을 찾는다.

격자마다 청소할 수 있는 최대 먼지량은 20이므로, MAP에 적혀있는 먼지를 그대로 더해서는 안된다.

먼지와 20 중 작은 칸을 비교하여 방향을 찾아야 한다.

전체 먼지 중 반대 방향(reverse)를 제외해서 최대 먼지량을 찾는다.

int min(int a, int b)
{
	return a < b ? a : b;
}

int getDirection(int index)
{
	RC target = cleaner[index];

	int total = MAP[target.r][target.c];
	for (int i = 0; i < 4; i++)
	{
		int nr, nc;

		nr = target.r + dr[i];
		nc = target.c + dc[i];
		
		if (MAP[nr][nc] == WALL) continue;

		total += min(MAP[nr][nc], 20);
	}

	int maxDir = -1;
	int maxDust = -1;

	int changeDir[] = { 2, 3, 0, 1 };

	for (int i = 0; i < 4; i++)
	{
		int reverse = changeDir[i];
		int nr, nc;

		nr = target.r + dr[reverse];
		nc = target.c + dc[reverse];

		int dust = total;

		if (MAP[nr][nc] != WALL) dust -= min(MAP[nr][nc], 20);
		
		if (maxDust < dust)
		{
			maxDust = dust;
			maxDir = i;
		}
	}

	return maxDir;
}

방향을 찾았다면 실제로 청소를 진행한다.

void clean(int index)
{
	int changeDir[] = { 2, 3, 0, 1 };

	RC target = cleaner[index];
	int direction = getDirection(index);

	if (direction == -1) return;

	int reverse = changeDir[direction];

	for (int i = 0; i < 4; i++)
	{
		if (i == reverse) continue;

		int nr, nc;

		nr = target.r + dr[i];
		nc = target.c + dc[i];

		if (MAP[nr][nc] == WALL) continue;

		MAP[nr][nc] -= 20;
		if (MAP[nr][nc] < 0) MAP[nr][nc] = 0;
	}

	MAP[target.r][target.c] -= 20;
	if (MAP[target.r][target.c] < 0) MAP[target.r][target.c] = 0;
}

3. 먼지 축적

먼지가 있는 칸에 먼지를 5 더한다.

void addDust()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 0 || MAP[r][c] == WALL) continue;

			MAP[r][c] += 5;
		}
	}
}

4. 먼지 확산

먼지가 없는 격자에 대해, 4방향 격자의 먼지량을 합한 후, 10으로 나눈 값을 추가하면 된다.

void spreadDust()
{
	int tmpMAP[MAX][MAX] = { 0 };
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] != 0) continue;

			int sum = 0;
			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				if (MAP[nr][nc] == WALL) continue;

				sum += MAP[nr][nc];
			}

			tmpMAP[r][c] = sum / 10;
		}
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == WALL) continue;

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

5. 출력

MAP에 있는 모든 먼지의 합을 더한다.

int getDust()
{
	int sum = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == WALL) continue;

			sum += MAP[r][c];
		}
	}

	return sum;
}

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (30 + 5)
#define WALL (-1)
#define INF (0x7fff0000)

#define RIGHT (0)
#define BOTTOM (1)
#define LEFT (2)
#define UP (3)

int T;
int N, K, L;

int MAP[MAX][MAX];
bool check[MAX][MAX]; // 청소기 좌표

struct RC
{
	int r;
	int c;
};

RC cleaner[50 + 5];
RC queue[MAX * MAX];

// →, ↓, ←, ↑
int dr[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };

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

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = WALL;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);

	for (int k = 1; k <= K; k++)
	{
		int r, c;

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

		cleaner[k].r = r;
		cleaner[k].c = c;
	}
}

void printMap() // for debug
{
	for (int k = 1; k <= K; k++)
		printf("%d] %d, %d\n", k, cleaner[k].r, cleaner[k].c);
	putchar('\n');

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

RC getDustRC(int index) // BFS
{
	RC ret;
	int rp, wp;
	int visit[MAX][MAX] = { 0 };

	rp = wp = 0;
	int sr = cleaner[index].r;
	int sc = cleaner[index].c;

	if (MAP[sr][sc] > 0) return { sr, sc };
	queue[wp].r = sr;
	queue[wp++].c = sc;

	visit[sr][sc] = 1;
	ret.r = ret.c = INF;
	int minDistance = INF;
	while (rp < wp)
	{
		RC out = queue[rp++];

		// 먼지를 찾은 경우 + 다른 청소기가 위치하지 않은 경우
		if (MAP[out.r][out.c] > 0 && check[out.r][out.c] == false)
		{
			if (visit[out.r][out.c] < minDistance)
			{
				minDistance = visit[out.r][out.c];
				ret = out;
			}
			else if (visit[out.r][out.c] == minDistance)
			{
				if (out.r < ret.r) ret = out;
				else if (out.r == ret.r)
				{
					if (out.c < ret.c)
						ret = out;
				}
			}

			continue;
		}

		for (int i = 0; i < 4; i++)
		{
			int nr, nc;

			nr = out.r + dr[i];
			nc = out.c + dc[i];

			if (MAP[nr][nc] == WALL || check[nr][nc] == true) continue;
			if (visit[nr][nc] != 0) continue;

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

			visit[nr][nc] = visit[out.r][out.c] + 1;
		}
	}

	if (ret.r == INF) return { sr, sc };

	return ret;
}

int min(int a, int b)
{
	return a < b ? a : b;
}

int getDirection(int index)
{
	RC target = cleaner[index];

	int total = MAP[target.r][target.c];
	for (int i = 0; i < 4; i++)
	{
		int nr, nc;

		nr = target.r + dr[i];
		nc = target.c + dc[i];
		
		if (MAP[nr][nc] == WALL) continue;

		total += min(MAP[nr][nc], 20);
	}

	int maxDir = -1;
	int maxDust = -1;

	int changeDir[] = { 2, 3, 0, 1 };

	for (int i = 0; i < 4; i++)
	{
		int reverse = changeDir[i];
		int nr, nc;

		nr = target.r + dr[reverse];
		nc = target.c + dc[reverse];

		int dust = total;

		if (MAP[nr][nc] != WALL) dust -= min(MAP[nr][nc], 20);
		
		if (maxDust < dust)
		{
			maxDust = dust;
			maxDir = i;
		}
	}

	return maxDir;
}

void clean(int index)
{
	int changeDir[] = { 2, 3, 0, 1 };

	RC target = cleaner[index];
	int direction = getDirection(index);

	if (direction == -1) return;

	int reverse = changeDir[direction];

	for (int i = 0; i < 4; i++)
	{
		if (i == reverse) continue;

		int nr, nc;

		nr = target.r + dr[i];
		nc = target.c + dc[i];

		if (MAP[nr][nc] == WALL) continue;

		MAP[nr][nc] -= 20;
		if (MAP[nr][nc] < 0) MAP[nr][nc] = 0;
	}

	MAP[target.r][target.c] -= 20;
	if (MAP[target.r][target.c] < 0) MAP[target.r][target.c] = 0;
}

void addDust()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 0 || MAP[r][c] == WALL) continue;

			MAP[r][c] += 5;
		}
	}
}

void spreadDust()
{
	int tmpMAP[MAX][MAX] = { 0 };
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] != 0) continue;

			int sum = 0;
			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				if (MAP[nr][nc] == WALL) continue;

				sum += MAP[nr][nc];
			}

			tmpMAP[r][c] = sum / 10;
		}
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == WALL) continue;

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

int getDust()
{
	int sum = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == WALL) continue;

			sum += MAP[r][c];
		}
	}

	return sum;
}

void simulate()
{
	for (int l = 0; l < L; l++)
	{
		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= N; c++)
				check[r][c] = 0; // 청소기 좌표 초기화

		// 0. 현재 청소기 좌표 체크
		for (int k = 1; k <= K; k++)
			check[cleaner[k].r][cleaner[k].c] = true;

		// 1. 청소기 이동
		for (int k = 1; k <= K; k++)
		{
			RC rc = getDustRC(k);

			check[cleaner[k].r][cleaner[k].c] = false;

			cleaner[k].r = rc.r;
			cleaner[k].c = rc.c;

			check[cleaner[k].r][cleaner[k].c] = true;
		}

		// 2. 청소
		for (int k = 1; k <= K; k++) clean(k);

		// 3. 먼지 축적
		addDust();

		// 4. 먼지 확산
		spreadDust();

		// 5. 출력
		printf("%d\n", getDust());		
	}
}

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

		simulate();
	}

	return 0;
}

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

[코드트리] 가로등 설치 (코드트리, 2025 하반기 오후 2번, B형) (1)	2025.12.18
[코드트리] 해적 선장 코디 (코드트리, 2025 하반기 오전 2번, B형) (0)	2025.12.15
[코드트리] 택배 하차 (삼성 SW 역량테스트 2025 하반기 오전 1번) (0)	2025.10.01
[코드트리] 여왕 개미 (삼성 SW 역량테스트 2025 상반기 오후 2번, B형) (0)	2025.05.01
[코드트리] 미생물 연구 (삼성 SW 역량테스트 2025 상반기 오후 1번) (0)	2025.05.01

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

[코드트리] AI 로봇청소기 (삼성 SW 역량테스트 2025 하반기 오후 1번)

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

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

댓글

티스토리툴바

[코드트리] AI 로봇청소기 (삼성 SW 역량테스트 2025 하반기 오후 1번)

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

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

관련글

댓글

티스토리툴바