BOJ 17825 : 주사위 윷놀이 (삼성 SW TEST A형)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/17825

 

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

 

시뮬레이션 문제는 시키는 대로 구현하면 된다.

 

이 문제에서는 파란색 화살표가 핵심이다. 파란색 화살표에 시작할 경우는 방향이 바뀌기 때문이다.

이런 경우는 그냥 처음부터 움직여야하는 방향에 대한 답을 적어두고 시작하면 된다.

 

먼저 왼쪽의 점수판은 오른쪽 그림처럼 번호를 매겨 1차원 배열로 만든다.

 

그러면 아래와 같이 input에서 미리 답을 적어둘 수 있다.

int dice[10 + 5];

int next[32 + 5][6];
int score[32 + 5];
int board[32 + 5];

int horse[5];

void input()
{
	for (int i = 1; i <= 10; i++) scanf("%d", &dice[i]);

	score[1] = 2; score[2] = 4; score[3] = 6; score[4] = 8; score[5] = 10;
	score[6] = 12; score[7] = 14; score[8] = 16; score[9] = 18; score[10] = 20;
	score[11] = 22; score[12] = 24; score[13] = 26; score[14] = 28; score[15] = 30;
	score[16] = 32; score[17] = 34; score[18] = 36; score[19] = 38; score[20] = 13;
	score[21] = 16; score[22] = 19; score[23] = 25; score[24] = 26; score[25] = 27;
	score[26] = 28;	score[27] = 24; score[28] = 22; score[29] = 30; score[30] = 35;
	score[31] = 40;

	next[0][1] = 1; next[0][2] = 2; next[0][3] = 3; next[0][4] = 4; next[0][5] = 5;

	next[1][1] = 2; next[1][2] = 3; next[1][3] = 4; next[1][4] = 5; next[1][5] = 6;
	next[2][1] = 3; next[2][2] = 4; next[2][3] = 5; next[2][4] = 6; next[2][5] = 7;
	next[3][1] = 4; next[3][2] = 5; next[3][3] = 6; next[3][4] = 7; next[3][5] = 8;
	next[4][1] = 5; next[4][2] = 6; next[4][3] = 7; next[4][4] = 8; next[4][5] = 9;
	next[5][1] = 20; next[5][2] = 21; next[5][3] = 22; next[5][4] = 23; next[5][5] = 29;
	next[6][1] = 7; next[6][2] = 8; next[6][3] = 9; next[6][4] = 10; next[6][5] = 11;
	next[7][1] = 8; next[7][2] = 9; next[7][3] = 10; next[7][4] = 11; next[7][5] = 12;
	next[8][1] = 9; next[8][2] = 10; next[8][3] = 11; next[8][4] = 12; next[8][5] = 13;
	next[9][1] = 10; next[9][2] = 11; next[9][3] = 12; next[9][4] = 13; next[9][5] = 14;
	next[10][1] = 28; next[10][2] = 27; next[10][3] = 23; next[10][4] = 29; next[10][5] = 30;

	next[11][1] = 12; next[11][2] = 13; next[11][3] = 14; next[11][4] = 15; next[11][5] = 16;
	next[12][1] = 13; next[12][2] = 14; next[12][3] = 15; next[12][4] = 16; next[12][5] = 17;
	next[13][1] = 14; next[13][2] = 15; next[13][3] = 16; next[13][4] = 17; next[13][5] = 18;
	next[14][1] = 15; next[14][2] = 16; next[14][3] = 17; next[14][4] = 18; next[14][5] = 19;
	next[15][1] = 26; next[15][2] = 25; next[15][3] = 24; next[15][4] = 23; next[15][5] = 29;
	next[16][1] = 17; next[16][2] = 18; next[16][3] = 19; next[16][4] = 31; next[16][5] = 32;
	next[17][1] = 18; next[17][2] = 19; next[17][3] = 31; next[17][4] = 32; next[17][5] = 32;
	next[18][1] = 19; next[18][2] = 31; next[18][3] = 32; next[18][4] = 32; next[18][5] = 32;
	next[19][1] = 31; next[19][2] = 32; next[19][3] = 32; next[19][4] = 32; next[19][5] = 32;
	next[20][1] = 21; next[20][2] = 22; next[20][3] = 23; next[20][4] = 29; next[20][5] = 30;

	next[21][1] = 22; next[21][2] = 23; next[21][3] = 29; next[21][4] = 30; next[21][5] = 31;
	next[22][1] = 23; next[22][2] = 29; next[22][3] = 30; next[22][4] = 31; next[22][5] = 32;
	next[23][1] = 29; next[23][2] = 30; next[23][3] = 31; next[23][4] = 32; next[23][5] = 32;
	next[24][1] = 23; next[24][2] = 29; next[24][3] = 30; next[24][4] = 31; next[24][5] = 32;
	next[25][1] = 24; next[25][2] = 23; next[25][3] = 29; next[25][4] = 30; next[25][5] = 31;
	next[26][1] = 25; next[26][2] = 24; next[26][3] = 23; next[26][4] = 29; next[26][5] = 30;
	next[27][1] = 23; next[27][2] = 29; next[27][3] = 30; next[27][4] = 31; next[27][5] = 32;
	next[28][1] = 27; next[28][2] = 23; next[28][3] = 29; next[28][4] = 30; next[28][5] = 31;
	next[29][1] = 30; next[29][2] = 31; next[29][3] = 32; next[29][4] = 32; next[29][5] = 32;
	next[30][1] = 31; next[30][2] = 32; next[30][3] = 32; next[30][4] = 32; next[30][5] = 32;

	next[31][1] = 32; next[31][2] = 32; next[31][3] = 32; next[31][4] = 32; next[31][5] = 32;
}

 

dice 배열 : 주사위에서 나올 수 있는 10개의 수, dice[1]부터 시작한다.

next 배열 : next[boardNumber][diceNumber]이며 현재의 board에서 주사위가 1 ~ 5가 나올 경우 가야할 다음 칸.

예를 들어 next[5][1]은 파란색 화살표이므로 바로 20으로 건너뛰게 된다.

next 배열은 board를 1차원 배열로 mapping한 그림을 보고 만들었다. 

 

score 배열 : score[boardNumber]이며 boardNumber에 저장될 점수

horse 배열 : 말이 현재 있는 위치를 저장하는 배열

---

DFS는 아래와 같이 만들면 된다.

int MAXANS = 0;
void DFS(int L, int S)
{
	if (L > 10)
	{
		if (MAXANS < S) MAXANS = S;
		return;
	}

	for (int i = 1; i <= 4; i++)
	{
		int current = horse[i]; /* 현재 말의 위치 */
		int nextPosition = next[current][dice[L]]; /* 말이 다음으로 갈 위치 */

		if (current == 32) continue;	
		if (nextPosition != 32 && board[nextPosition]) continue;
		
		horse[i] = nextPosition;
		board[current] = 0;
		board[nextPosition] = 1;
		
		DFS(L + 1, S + score[horse[i]]);

		horse[i] = current;
		board[current] = 1;
		board[nextPosition] = 0;
	}
}

 

Level이 10이 넘으면 주사위 10번을 모두 사용한 경우이므로 최종 점수를 갱신한다.

 

현재 말의 위치가 32(도착점)면 도착한 말이므로 다음 말로 넘어간다.

nextPostion은 dice[L]을 보고 다음으로 갈 board의 번호이다.

여기에 말이 있다면 다음 말로 넘어가 continue이지만, 32인 경우는 무시해야 한다.

 

말이 움직일 수 있다면, 말의 현재 위치는 0으로 변경하고, 다음 위치에는 1로 check해둔다.

DFS가 종료되면 원상복구하면 된다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

int dice[10 + 5];

int next[32 + 5][6];
int score[32 + 5];
int board[32 + 5];

int horse[5];

void input()
{
	for (int i = 1; i <= 10; i++) scanf("%d", &dice[i]);

	score[1] = 2; score[2] = 4; score[3] = 6; score[4] = 8; score[5] = 10;
	score[6] = 12; score[7] = 14; score[8] = 16; score[9] = 18; score[10] = 20;
	score[11] = 22; score[12] = 24; score[13] = 26; score[14] = 28; score[15] = 30;
	score[16] = 32; score[17] = 34; score[18] = 36; score[19] = 38; score[20] = 13;
	score[21] = 16; score[22] = 19; score[23] = 25; score[24] = 26; score[25] = 27;
	score[26] = 28;	score[27] = 24; score[28] = 22; score[29] = 30; score[30] = 35;
	score[31] = 40;

	next[0][1] = 1; next[0][2] = 2; next[0][3] = 3; next[0][4] = 4; next[0][5] = 5;

	next[1][1] = 2; next[1][2] = 3; next[1][3] = 4; next[1][4] = 5; next[1][5] = 6;
	next[2][1] = 3; next[2][2] = 4; next[2][3] = 5; next[2][4] = 6; next[2][5] = 7;
	next[3][1] = 4; next[3][2] = 5; next[3][3] = 6; next[3][4] = 7; next[3][5] = 8;
	next[4][1] = 5; next[4][2] = 6; next[4][3] = 7; next[4][4] = 8; next[4][5] = 9;
	next[5][1] = 20; next[5][2] = 21; next[5][3] = 22; next[5][4] = 23; next[5][5] = 29;
	next[6][1] = 7; next[6][2] = 8; next[6][3] = 9; next[6][4] = 10; next[6][5] = 11;
	next[7][1] = 8; next[7][2] = 9; next[7][3] = 10; next[7][4] = 11; next[7][5] = 12;
	next[8][1] = 9; next[8][2] = 10; next[8][3] = 11; next[8][4] = 12; next[8][5] = 13;
	next[9][1] = 10; next[9][2] = 11; next[9][3] = 12; next[9][4] = 13; next[9][5] = 14;
	next[10][1] = 28; next[10][2] = 27; next[10][3] = 23; next[10][4] = 29; next[10][5] = 30;

	next[11][1] = 12; next[11][2] = 13; next[11][3] = 14; next[11][4] = 15; next[11][5] = 16;
	next[12][1] = 13; next[12][2] = 14; next[12][3] = 15; next[12][4] = 16; next[12][5] = 17;
	next[13][1] = 14; next[13][2] = 15; next[13][3] = 16; next[13][4] = 17; next[13][5] = 18;
	next[14][1] = 15; next[14][2] = 16; next[14][3] = 17; next[14][4] = 18; next[14][5] = 19;
	next[15][1] = 26; next[15][2] = 25; next[15][3] = 24; next[15][4] = 23; next[15][5] = 29;
	next[16][1] = 17; next[16][2] = 18; next[16][3] = 19; next[16][4] = 31; next[16][5] = 32;
	next[17][1] = 18; next[17][2] = 19; next[17][3] = 31; next[17][4] = 32; next[17][5] = 32;
	next[18][1] = 19; next[18][2] = 31; next[18][3] = 32; next[18][4] = 32; next[18][5] = 32;
	next[19][1] = 31; next[19][2] = 32; next[19][3] = 32; next[19][4] = 32; next[19][5] = 32;
	next[20][1] = 21; next[20][2] = 22; next[20][3] = 23; next[20][4] = 29; next[20][5] = 30;

	next[21][1] = 22; next[21][2] = 23; next[21][3] = 29; next[21][4] = 30; next[21][5] = 31;
	next[22][1] = 23; next[22][2] = 29; next[22][3] = 30; next[22][4] = 31; next[22][5] = 32;
	next[23][1] = 29; next[23][2] = 30; next[23][3] = 31; next[23][4] = 32; next[23][5] = 32;
	next[24][1] = 23; next[24][2] = 29; next[24][3] = 30; next[24][4] = 31; next[24][5] = 32;
	next[25][1] = 24; next[25][2] = 23; next[25][3] = 29; next[25][4] = 30; next[25][5] = 31;
	next[26][1] = 25; next[26][2] = 24; next[26][3] = 23; next[26][4] = 29; next[26][5] = 30;
	next[27][1] = 23; next[27][2] = 29; next[27][3] = 30; next[27][4] = 31; next[27][5] = 32;
	next[28][1] = 27; next[28][2] = 23; next[28][3] = 29; next[28][4] = 30; next[28][5] = 31;
	next[29][1] = 30; next[29][2] = 31; next[29][3] = 32; next[29][4] = 32; next[29][5] = 32;
	next[30][1] = 31; next[30][2] = 32; next[30][3] = 32; next[30][4] = 32; next[30][5] = 32;

	next[31][1] = 32; next[31][2] = 32; next[31][3] = 32; next[31][4] = 32; next[31][5] = 32;
}

int MAXANS = 0;
void DFS(int L, int S)
{
	if (L > 10)
	{
		if (MAXANS < S) MAXANS = S;
		return;
	}

	for (int i = 1; i <= 4; i++)
	{
		int current = horse[i];
		int nextPosition = next[current][dice[L]];

		if (current == 32) continue;	
		if (nextPosition != 32 && board[nextPosition]) continue;
		
		horse[i] = nextPosition;
		board[current] = 0;
		board[nextPosition] = 1;
		
		DFS(L + 1, S + score[horse[i]]);

		horse[i] = current;
		board[current] = 1;
		board[nextPosition] = 0;
	}
}

int main(void)
{
	input();

	DFS(1, 0);

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

	return 0;
}

 

실제 A형에서는 답을 미리 저장하는 코드는 init함수에서 만들어 1번만 실행하도록 한다.