[코드트리] 술래잡기 체스 (삼성 SW 역량테스트 2020 상반기 오전 2번)

삼성 A형 전체 링크

 

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

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

 

술래잡기 체스 문제 풀이는 BOJ 19236 : 청소년 상어와 같다.

#include <stdio.h>

int T;
int MAP[6][6];

typedef struct st2
{
	int r;
	int c;
	int dir;
	int dead;
}CHESS;

CHESS horse[17];

int dr[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int changeDir[] = { 0, 2, 3, 4, 5, 6, 7, 8, 1 };

int maxAnswer;

void input()
{
	for (int r = 0; r <= 5; r++)
		for (int c = 0; c <= 5; c++)
			MAP[r][c] = -1; /* 벽 표시 */

	for (int r = 1; r <= 4; r++)
	{
		for (int c = 1; c <= 4; c++)
		{
			int number, dir;

			scanf("%d %d", &number, &dir);

			MAP[r][c] = number;

			horse[number].r = r;
			horse[number].c = c;
			horse[number].dir = dir;
		}
	}
}

void output(CHESS tag, int map[6][6], CHESS fish[], int score)
{
	printf("tag : r %d, c %d, dir %d score %d\n", tag.r, tag.c, tag.dir, score);
	printf("live : ");
	for (int i = 1; i <= 16; i++)
		if (fish[i].dead == 0) printf("%d, ", i);
	putchar('\n');

	for (int r = 1; r <= 4; r++)
	{
		for (int c = 1; c <= 4; c++)
		{
			if (r == tag.r && c == tag.c) printf("(%d, %d) ", -1, tag.dir);
			else printf("(%d, %d) ", map[r][c], fish[map[r][c]].dir);

		}
		putchar('\n');
	}
	putchar('\n');
}

void DFS(int sr, int sc, int dir, int score, int map[6][6], CHESS fish[])
{
	int tmpMAP[6][6];
	CHESS tag = { 0 };
	CHESS tmpHorse[17] = { 0 };

	for (int r = 0; r <= 5; r++)
		for (int c = 0; c <= 5; c++)
			tmpMAP[r][c] = map[r][c];

	for (int i = 1; i <= 16; i++) tmpHorse[i] = fish[i];

	if (tmpHorse[tmpMAP[sr][sc]].dead == 1) return; /* 물고기가 없는 경우 */

	tag.r = sr;
	tag.c = sc;

	int deadHorseNumber = tmpMAP[sr][sc]; /* 상어에게 잡아 먹힌 물고기의 번호 */

	tag.dir = tmpHorse[deadHorseNumber].dir;

	score += deadHorseNumber; /* 물고기 합 갱신 */
	tmpHorse[deadHorseNumber].dead = 1; /* 물고기 dead 표시 */

	for (int number = 1; number <= 16; number++)
	{
		CHESS f = tmpHorse[number];

		if (f.dead) continue;

		while (1)
		{
			int nr, nc;

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

			if (tmpMAP[nr][nc] == -1 || (nr == tag.r && nc == tag.c))
			{
				tmpHorse[number].dir = f.dir = changeDir[f.dir];
				continue;
			}
			else
			{
				int changeHorseNumber = tmpMAP[nr][nc];

				int tmpR, tmpC;

				tmpR = tmpHorse[number].r;
				tmpHorse[number].r = tmpHorse[changeHorseNumber].r;
				tmpHorse[changeHorseNumber].r = tmpR;

				tmpC = tmpHorse[number].c;
				tmpHorse[number].c = tmpHorse[changeHorseNumber].c;
				tmpHorse[changeHorseNumber].c = tmpC;

				int tmp = tmpMAP[nr][nc];
				tmpMAP[nr][nc] = tmpMAP[f.r][f.c];
				tmpMAP[f.r][f.c] = tmp;

				break;
			}
		}
	}

	for (int move = 1; move <= 3; move++)
	{
		int nr, nc;

		nr = tag.r + dr[tag.dir] * move;
		nc = tag.c + dc[tag.dir] * move;

		if (map[nr][nc] == -1)
		{
			if (maxAnswer < score) maxAnswer = score;
			break; /* 더 이상 움직일 수 없는 경우 종료 */
		}

		DFS(nr, nc, tag.dir, score, tmpMAP, tmpHorse);
	}
}

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

		DFS(1, 1, 0, 0, MAP, horse);

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

	return 0;
}