[코드트리] 승자독식 모노폴리 (삼성 SW 역량테스트 2020 상반기 오후 1번)

 

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/odd-monopoly

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

 

승자독식 모노폴리 문제 풀이는 BOJ 19237 : 어른 상어와 같다.

#include <stdio.h>

#define MAX (20 + 5)

int T;
int N, M, K;

typedef struct st1
{
	int number;
	int current;
	int time;
}INFO;

INFO MAP[MAX][MAX];

typedef struct st2
{
	int r;
	int c;
	int dir;
	int priority[5][5];
	int dead;
}PLAYER;

PLAYER player[MAX * MAX];

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

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

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

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int in;

			scanf("%d", &in);

			if (in)
			{
				player[in].r = r;
				player[in].c = c;
			}
		}
	}

	for (int i = 1; i <= M; i++)
	{
		int dir;
		scanf("%d", &dir);
		player[i].dir = dir;
	}

	for (int i = 1; i <= M; i++)
		for (int d = 1; d <= 4; d++)
			scanf("%d %d %d %d", &player[i].priority[d][1], &player[i].priority[d][2], &player[i].priority[d][3], &player[i].priority[d][4]);
}

void output()
{
	for (int i = 1; i <= M; i++)
		printf("player[%d] : r %d, c %d, dir %d, dead %d\n", i, player[i].r, player[i].c, player[i].dir, player[i].dead);
	putchar('\n');

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int current = 0;
			for (int s = 1; s <= M; s++)
				if (r == player[s].r && c == player[s].c) current = s;

			printf("(%d, %d, %d) ", MAP[r][c].number, MAP[r][c].time, current);
		}
		putchar('\n');
	}
	putchar('\n');
}

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

int findDirection(PLAYER player, int number)
{
	int currentDir = player.dir;

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

		nextDir = player.priority[currentDir][d]; /* 우선순위에 대한 다음 좌표 */
		nr = player.r + dr[nextDir];
		nc = player.c + dc[nextDir];

		if (MAP[nr][nc].number == -1) continue; /* 벽인 경우 */
		if (MAP[nr][nc].time == 0) return nextDir; /* 아무 냄새가 없는 경우 */
	}

	/* 벽이거나 주변에 모두 냄새가 있는 경우 */
	for (int d = 1; d <= 4; d++)
	{
		/* 자신의 체취 찾기 */

		int nr, nc, nextDir;

		nextDir = player.priority[currentDir][d];
		nr = player.r + dr[nextDir];
		nc = player.c + dc[nextDir];

		if (MAP[nr][nc].number == number) return nextDir;
	}

	printf("impossible case!\n");
	return -1; /* error */
}

int simulate()
{
	int playerCount = M;
	for (int t = 1; t <= 1000; t++)
	{
		/* 냄새 뿌리기 */
		for (int s = 1; s <= M; s++)
		{
			if (player[s].dead) continue;

			MAP[player[s].r][player[s].c].number = s;
			MAP[player[s].r][player[s].c].time = K;
		}

		/* 이동 및 상어 dead 처리 */
		for (int s = 1; s <= M; s++)
		{
			if (player[s].dead) continue;

			int nr, nc, dir;

			dir = findDirection(player[s], s);

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

			if (MAP[nr][nc].current) /* 이미 상어가 있는 경우 */
			{
				int alreadySharkNumber = MAP[nr][nc].current;

				playerCount--;

				if (alreadySharkNumber < s) player[s].dead = 1;
				else
				{
					player[alreadySharkNumber].dead = 1;

					player[s].r = nr;
					player[s].c = nc;
					player[s].dir = dir;

					MAP[nr][nc].current = s;
					MAP[nr][nc].number = s;
				}
			}
			else
			{
				player[s].r = nr;
				player[s].c = nc;
				player[s].dir = dir;

				MAP[nr][nc].current = s;
				MAP[nr][nc].number = s;
			}
		}

		for (int s = 1; s <= M; s++) MAP[player[s].r][player[s].c].current = 0;

		/* 한 마리만 남은 경우 종료 */
		if (playerCount == 1) return t;

		/* time 감소 */
		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= N; c++)
				if (MAP[r][c].time) MAP[r][c].time--;
	}

	return -1;
}

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

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

	return 0;
}