[코드트리] 이상한 윷놀이 (삼성 SW 역량테스트 2019 하반기 오전 2번)

 

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

 

삼성 A형 전체 링크

 

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

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

 

이상한 윷놀이 문제 풀이는 BOJ 17837 : 새로운 게임 2와 같다.

#include <stdio.h>

#define MAX (12 + 5)

#define WHITE (0)
#define RED (1)
#define BLUE (2)

int T;
int N, K;
int MAP[MAX][MAX];

typedef struct st1
{
	int r;
	int c;
	int dir;
	int index;
}HORSE;

HORSE horse[12];
int hcnt;

int deque[MAX][MAX][50];
// int front[MAX][MAX];
int back[MAX][MAX];

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

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

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

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

	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			back[r][c] = 0;

	hcnt = 1;
	for (int i = 0; i < K; i++)
	{
		int r, c, dir;

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

		horse[hcnt].r = r;
		horse[hcnt].c = c;
		horse[hcnt].dir = dir;
	
		int& wp = back[r][c];

		deque[r][c][wp] = hcnt;
		horse[hcnt].index = wp;

		wp++;
		hcnt++;
	}
}

void moveWhite(int horseNumber)
{
	HORSE& hor = horse[horseNumber];
	int nr, nc, nowr, nowc;

	nr = hor.r + dr[hor.dir];
	nc = hor.c + dc[hor.dir];
	nowr = hor.r;
	nowc = hor.c;

	int nowFront = hor.index;
	int& nowBack = back[hor.r][hor.c];
	int& nextBack = back[nr][nc];

	for (int k = nowFront; k < nowBack; k++)
	{
		int dhorse = deque[nowr][nowc][k]; /* 현재 좌표의 deque에 있는 말 */

		horse[dhorse].r = nr; /* 말들의 좌표 이동 */
		horse[dhorse].c = nc;
		horse[dhorse].index = nextBack;

		deque[nr][nc][nextBack++] = dhorse; /* 다음 deque에도 저장 */
	}

	nowBack = nowFront; /* 현재 deque에서 이동한 말들을 삭제 */
}

void moveRed(int horseNumber)
{
	HORSE& hor = horse[horseNumber];
	int nr, nc, nowr, nowc;

	nr = hor.r + dr[hor.dir];
	nc = hor.c + dc[hor.dir];
	nowr = hor.r;
	nowc = hor.c;

	int nowFront = hor.index;
	int& nowBack = back[hor.r][hor.c];
	int& nextBack = back[nr][nc];

	for (int k = nowBack - 1; k >= nowFront; k--)
	{
		int dhorse = deque[nowr][nowc][k]; /* 현재 좌표의 deque에 있는 말 */

		horse[dhorse].r = nr; /* 말들의 좌표 이동 */
		horse[dhorse].c = nc;
		horse[dhorse].index = nextBack;

		deque[nr][nc][nextBack++] = dhorse; /* 다음 deque에도 저장 */
	}

	nowBack = nowFront; /* 현재 deque에서 이동한 말들을 삭제 */
}

int simulation()
{
	int changeDir[5] = { 0, 2, 1, 4, 3 };

	for (int i = 1; i <= 1000; i++)
	{
		/* 말 하나씩 이동 */
		for (int h = 1; h < hcnt; h++)
		{

			int nr, nc;
			HORSE& hor = horse[h];

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

			if (MAP[nr][nc] == WHITE) moveWhite(h);
			else if (MAP[nr][nc] == RED) moveRed(h);
			else /* BLUE */
			{
				int cr, cc;

				hor.dir = changeDir[hor.dir];

				cr = hor.r + dr[hor.dir];
				cc = hor.c + dc[hor.dir];

				if (MAP[cr][cc] == WHITE) moveWhite(h);
				else if (MAP[cr][cc] == RED) moveRed(h);
				/* BLUE는 아무 일도 하지 않으므로 생략 */
			}

			/* 턴이 진행되던 중에 말이 4개 이상인지 check */
			if (back[hor.r][hor.c] >= 4) return i;
		}
	}

	return -1;
}

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

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

	return 0;
}