[코드트리] 전투 로봇 (삼성 SW 역량테스트 2018 하반기 오후 2번)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/fighting-robot

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

 

전투 로봇 문제 풀이는 BOJ 16236 : 아기 상어와 같다.

#include <stdio.h>

#define MAX (20 + 10)

int T;
int N;
int MAP[MAX][MAX];
int visit[MAX][MAX];

typedef struct st1
{
	int r;
	int c;
	int eat;
	int size;
}ROBOT;

ROBOT attackRobot;

typedef struct st2
{
	int r;
	int c;
}QUEUE;

QUEUE queue[MAX * MAX];
int wp, rp;

int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

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

			if (MAP[r][c] == 9)
			{
				MAP[r][c] = 0; /* 자기 자신을 통과하도록 0으로 변경 */
				attackRobot.r = r;
				attackRobot.c = c;
				attackRobot.eat = 0;
				attackRobot.size = 2;
			}
		}
	}
}

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

int checkMonster()
{
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			if (MAP[r][c] != 0 && MAP[r][c] < attackRobot.size) return 1;

	return 0;
}

int BFS(int er, int ec)
{
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			visit[r][c] = 0;

	wp = rp = 0;

	queue[wp].r = attackRobot.r;
	queue[wp++].c = attackRobot.c;

	visit[attackRobot.r][attackRobot.c] = 1;

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

		if (out.r == er && out.c == ec) return visit[out.r][out.c] - 1;

		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;
			if (MAP[nr][nc] > attackRobot.size) continue;

			if (visit[nr][nc] == 0) /* 벽이 아니고, 방문 하지 않은 곳 */
			{
				queue[wp].r = nr;
				queue[wp++].c = nc; /* push */

				visit[nr][nc] = visit[out.r][out.c] + 1; /* 방문 check + 거리 계산 */
			}
		}
	}

	return 0x7fff0000;
}

int allBFS()
{
	if (checkMonster() == 0) return 0; /* 잡아먹을 수 있는 물고기가 없는 경우 종료 */

	int tmpR, tmpC;

	int min = 0x7fff0000;
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			if (MAP[r][c] == 0) continue;
			if (MAP[r][c] >= attackRobot.size) continue;

			int length = BFS(r, c);
			if (length < min)
			{
				min = length;

				tmpR = r; /* 잡아 먹을 물고기의 임시 좌표 */
				tmpC = c;
			}
		}
	}

	if (min == 0x7fff0000) return 0; /* 물고기가 있지만 잡을 수 없는 경우 */

	MAP[tmpR][tmpC] = 0; /* 물고기 제거 */

	attackRobot.r = tmpR; /* 물고기 좌표로 이동 */
	attackRobot.c = tmpC;
	attackRobot.eat++;

	if (attackRobot.eat == attackRobot.size)
	{
		attackRobot.eat = 0;
		attackRobot.size++;
	}

	return min;
}

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

		int time = 0;

		while (1)
		{
			int ret = allBFS();

			if (ret == 0) break;

			time += ret;
		}

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

	return 0;
}