[백준] 17825번: 주사위 윷놀이

https://www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

 

문제 이해

윷놀이 판을 어떻게 표현해야할지가 고민되었다.

 

출발부터 도착까지 가는 경로는 이렇게 5가지가 있으니까 이 경로들을 배열로 만들어주었다. 

초록색 경로는 0번, 파란색 경로는 1번, 주황색 경로는 2번, 노란색 경로는 3번이다.

말은 초록색 경로의 10, 20, 30칸에 도착하면 r[0] 번 길에서 각 r[1], r[2], r[3]번 도로로 가게 된다.

 

그리고 4개의 말의 위치와 정보를 저장할 배열 mal을 만들었다. 

각 말에 live라는 변수를 추가해서, 말이 도착점에 도착하면 0, 즉 더이상 안움직이는 말이라는 것을 표시해줬다.

DFS()

각 회에 어떤 말을 움직일지를 결정한다. 최대 10회이기 때문에 DFS로 충분히 가능하다.

Already_Exists()

말이 있는지를 확인한다.

이때 맵(r)이 좀 복잡해서 말이 맵 위에 있는지를 판단하는 것이 힘들다.

동그라미 친 곳들이 중복되는 곳이다. 

일단 마지막으로 건너는 길 (25, 30, 35)은 r[1], r[2], r[3]에 모두 겹치고,

40은 r[0], r[1], r[2], r[3] 에 겹친다.

 

그래서 이 겹치는 칸들은 단순히 맵에서 숫자가 같은 경우로 처리를 했다.

        r[길][칸] == r[길][칸]

 

그러면 하나 더 문제가 생기는게, 

r[0]의 우측에 있는 30과 r[1], r[2], r[3] 에 있는 30을 같은 칸으로 처리를 하게 된다는 것이다. (초록 동그라미)

 

그래서 여기에 대한 예외처리를 하나 더 추가했다. 

int Already_Exists(int i) {
	for (int j = 0; j < 4; j++) {
		if (i == j) continue;
		if (mal[j].live == 0) continue;
		if (mal[j].road == mal[i].road && mal[j].idx == mal[i].idx) return 1;
		// 25, 30, 35, 40은 안됨 - 30이 또 문제임
		if (r[mal[j].road][mal[j].idx] == 40 && r[mal[i].road][mal[i].idx] == 40) return 1;
		if (r[mal[j].road][mal[j].idx] == 25 && r[mal[i].road][mal[i].idx] == 25) return 1;
		if (r[mal[j].road][mal[j].idx] == 35 && r[mal[i].road][mal[i].idx] == 35) return 1;
		if (r[mal[j].road][mal[j].idx] == 30 && r[mal[i].road][mal[i].idx] == 30) {
			// 둘다 30인데, 한쪽이 idx 가 0이면 아님
			if (mal[j].idx != 0 && mal[i].idx != 0) return 1;
		}
	}
	return 0;
}

똑같이 칸이 30인데, 인덱스가 0 이면 r[4][0]의 30이지 r[4][5] == r[1][4] == r[2][5] 의 30이 아니기 때문이다. (같은 칸이 아니라는 뜻)

 

그리고 또 하나 주의할 점은 말이 도착점 이후로 말이 이동하고 나면 이 말은 이제 중복 처리에 들어가면 안되서, 

if(mal[j].live == 0) 의 조건문을 추가해줬다!

 

위에 있는 같은 칸인지 판단하는 게 조금 예외처리할 게 많아서 어려운 문제였다.

 

전체 코드

#include <stdio.h>
#include <string.h>

int r[4][21+5+2] = {{ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26,
			28, 30, 32, 34, 36, 38, 40 }, 
			{ 10, 13, 16, 19, 25, 30, 35, 40},
			{ 20, 22, 24, 25, 30, 35, 40 },
			{ 30, 28, 27, 26, 25, 30, 35, 40 }};

typedef struct str1 {
	int road;
	int idx; // 위치 정보
	int live;
}M;
M mal[4];
int dice[10 + 2];
int max_pnt;
int select[10 + 2];

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

void Init(void) {
	for (int i = 0; i < 4; i++) {
		mal[i].live = 1;
	}
}

int Already_Exists(int i) {
	for (int j = 0; j < 4; j++) {
		if (i == j) continue;
		if (mal[j].live == 0) continue;
		if (mal[j].road == mal[i].road && mal[j].idx == mal[i].idx) return 1;
		// 25, 30, 35, 40은 안됨 - 30이 또 문제임
		if (r[mal[j].road][mal[j].idx] == 40 && r[mal[i].road][mal[i].idx] == 40) return 1;
		if (r[mal[j].road][mal[j].idx] == 25 && r[mal[i].road][mal[i].idx] == 25) return 1;
		if (r[mal[j].road][mal[j].idx] == 35 && r[mal[i].road][mal[i].idx] == 35) return 1;
		if (r[mal[j].road][mal[j].idx] == 30 && r[mal[i].road][mal[i].idx] == 30) {
			// 둘다 30인데, 한쪽이 idx 가 0이면 아님
			if (mal[j].idx != 0 && mal[i].idx != 0) return 1;
		}
	}
	return 0;
}

void DFS(int turn, int pnt) {

	// 종료
	if (turn == 10) {
		// 다 정했음
		if (pnt > max_pnt) max_pnt = pnt;
		return;
	}

	// 반복
	for (int i = 0; i < 4; i++) {
		if (mal[i].live == 0) continue; // 이미 끝난 말
		int flag = 1;
		// i번째 말을 움직인다
		M tmp = mal[i];
		mal[i].idx += dice[turn];
		if (mal[i].road == 0) {
			if (mal[i].idx == 5) { mal[i].idx = 0, mal[i].road = 1; }
			if (mal[i].idx == 10) { mal[i].idx = 0, mal[i].road = 2; }
			if (mal[i].idx == 15) { mal[i].idx = 0, mal[i].road = 3; }
		}
		// 지금 위치에 다른 말이 있는지 확인
		if(Already_Exists(i)) ;
		
		if (Already_Exists(i)) { // 말이 있음 -> 갈 수 없음
			mal[i] = tmp; // 원래대로 돌림
			continue;
		}
		// 이 말이 끝났는지 확인
		if (r[mal[i].road][mal[i].idx] == 0) {
			mal[i].live = 0;
		}
		// pnt 를 얻고 다음 turn
		int npnt = pnt + r[mal[i].road][mal[i].idx];
		select[turn] = i;
		DFS(turn + 1, npnt);
		// 원래 말의 상태로 돌아오기
		mal[i] = tmp;
	}
}

int main(void) {
	//freopen("in.txt", "r", stdin);
	Get_Input();
	Init();
	DFS(0, 0);
	printf("%d", max_pnt);
	return 0;
}