BOJ 17837 : 새로운 게임 2 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/17837

 

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

 

덱(deque)를 사용하여 풀이를 하지만, 실제 덱 사용법과는 다르게 풀어본다. (단순 배열이라고 생각하는 것이 좋다.)

나무 재테크와는 달리 덱의 앞 부분에 push/pop되는 경우가 없다.

 

현재 이동하는 말부터 모두 옮기고, 다음 칸에 넣을 때, 순서대로 넣거나, 반대로 넣는 차이만 있을 뿐,

다음 칸의 말의 앞부분에 넣지는 않는다.

 

따라서 초기의 front와 back을 0으로 초기화해도 된다.

 

구현 방법은 아래와 같다.

 

다음 칸이 WHITE 면, moveWhite를 한다.

다음 칸이 RED 면, moveRed를 한다.

다음 칸이 BLUE 면, 방향을 바꾼 후, 다음 칸을 체크해서

→ WHITE 면 moveWhite를 실행

→ RED 면 moveRed를 실행

 

먼저 input 함수를 보자.

#define MAX (12 + 5)

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

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];

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]);

	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++;
	}
}

 

말에는 현재 좌표와 방향, 그리고 deque에 저장할 index를 구조체로 만든다.

index를 저장해둬야, deque에서 현재 말부터 위의 말까지 쉽게 접근할 수 있다.

 

벽을 저장하는 MAP과 말을 저장하는 deque[r][c][50]을 선언한다. 말은 최대 10개이므로 넉넉하게 50으로 잡았다.

그리고 deque의 index front[r][c]와 back[r][c]를 선언한다.

 

벽을 만나면 BLUE와 같은 행동을 해야하므로 주변을 BLUE로 만들고 (1, 1)부터 입력을 받는다.

 

그리고 말 구조체에는 좌표와 방향을 입력받고, deque에는 말의 번호를 저장한다.

deque에 저장되는 index를 말에도 저장하는 것을 잊지 말자.

---

이제 시뮬레이션을 해보자.

1000번 동안 시뮬레이션 해도 게임이 종료(말이 4개 이상 겹침)되지 않으면 for문을 빠져나가고 -1을 return 한다.

방향 전환을 위한 배열 changeDir을 선언하여 chg[1] = 2, chg[2] = 1, chg[3] = 4, chg[4] = 3가 되도록 한다.

dr, dc를 이용하여 말을 움직이고, 말의 다음 칸의 색을 보고 move한다.

BLUE인 경우 방향을 전환하고 한 칸 더 움직이므로, 한 칸 더 움직이는 칸의 색깔도 확인하여 move하면 된다.

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

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;
}

턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료되므로, 매번 말을 움직일 때마다, 4개의 말인지 check한다.

말은 항상 0번부터 존재하므로 back[현재 말의 row][현재 말의 column]이 (r, c)에 있는 말의 수가 된다.

---

이제 moveWhite를 구현해보자. 말의 번호를 넘겨받아서 작동하게 된다.

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에서 이동한 말들을 삭제 */
}

 

넘겨받은 말의 deque 좌표는 horse[r][c].index에 저장을 해두었으므로,

그 index부터 deque의 끝(nowBack)까지 순서대로 말이 쌓여있다. 그대로 말 한 마리씩 움직이면 된다.

 

순서대로 다음 칸(nr, nc)의 deque에 back[nr][nc]를 이용하여서 deque에 쌓아두자.

마지막으로 deque[r][c]에서는 말을 제거해야하므로 nowBack을 nowFront과 같게 만들어 준다.

다음 좌표에서 nowBack이 nowFront가 되었으므로 더 이상 뒷부분의 배열에 접근할 수 없다.

(reference & 이므로 nowBack → back[hor.r][hor.c]가 변경된다.) 

 

moveRed도 동일하지만 거꾸로 쌓기만 하면 된다. moveRed는 전체 코드를 참고하자.

(nowBack - 1부터 nowFront까지 거꾸로 넣으면 된다.)

#include <stdio.h>

#define MAX (12 + 5)

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

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];

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]);

	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++;
	}
}

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

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)
{
	input();

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

	return 0;
}

 

실제 A형에서는 tc가 여러 개이므로, front와 back을 0으로 초기화하는 코드를 추가해야 한다.