백준 17825번 _ 주사위 윷놀이

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

17825번: 주사위 윷놀이

 

풀이방법

이 문제는 일단 윷놀이판이 고정이므로, 윷놀이 판과 어떻게 이어지는지를 먼저 만들었다.

윷놀이판 빨간색글씨는 idx

위의 그림을 밑의 코드로 옮겼다고 생각하면된다.

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

void makeEdge()
{
	//1
	edge.resize(43);
	for (int i = 0; i < 20; i++)
		edge[i].push_back(i + 1);

	//2
	edge[5].push_back(21);
	for (int i = 21; i < 24; i++)
		edge[i].push_back(i + 1);

	//3
	edge[10].push_back(25);
	edge[25].push_back(26);
	edge[26].push_back(24);

	//4
	edge[15].push_back(27);
	edge[27].push_back(28);
	edge[28].push_back(29);
	edge[29].push_back(24);

	//5
	edge[24].push_back(30);
	edge[30].push_back(31);
	edge[31].push_back(20);

	//32가 도착지
	edge[20].push_back(32);
}

 

 그리고 교차점 같은경우에는 edge에 [0]에는 빨간색길, [1]에는 파란색길로 통일하여 간단하게 구현할수 있었다.

 

 그리고 나서는 이 문제의 시간을 봤는데 1초 (약 1억)여서 완전탐색해도 4^10이므로 시간은 생각하지 않고 dfs를 이용한 완전탐색으로 풀었다. 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int board[35];
int boardScore[35] = { 0,2,4,6,8,10,12,14,16,18,20,22, 24,26,28,30,32,34,36,38,40,
							13,16,19,25,22,24,28,27,26,30,35,0 };
vector<vector<int>> edge;
int destination = 32;
int dice[11];

void diceInput()
{
	int value;
	for (int i = 0; i < 10; i++)
	{
		cin >> value;
		dice[i] = value;
	}
}

void makeEdge()
{
	//1
	edge.resize(43);
	for (int i = 0; i < 20; i++)
		edge[i].push_back(i + 1);

	//2
	edge[5].push_back(21);
	for (int i = 21; i < 24; i++)
		edge[i].push_back(i + 1);

	//3
	edge[10].push_back(25);
	edge[25].push_back(26);
	edge[26].push_back(24);

	//4
	edge[15].push_back(27);
	edge[27].push_back(28);
	edge[28].push_back(29);
	edge[29].push_back(24);

	//5
	edge[24].push_back(30);
	edge[30].push_back(31);
	edge[31].push_back(20);

	//32가 도착지
	edge[20].push_back(32);
}

int result = 0;
void dfs(int checkMarker, int diceCnt, int sum, map<int, int>markerPoint)
{
	if (diceCnt > 9)
	{
		result = max(result, sum);
		return;
	}

	int originalPos = markerPoint[checkMarker];
	int markerPos = markerPoint[checkMarker];
	int moveCnt = dice[diceCnt];

	//움직이자 ㄱㄱ
	//움직이기전에 내가 있는위치가 갈림길인지 아닌지 확인
	if (edge[markerPos].size() == 2)
		markerPos =edge[markerPos][1];
	else
		markerPos = edge[markerPos][0];

	for (int i = 1; i < moveCnt; i++)
	{
		if (markerPos == 32)
			break;
		markerPos = edge[markerPos][0];
	}

	//도착한 곳에 말이 있으면 안됨, 도착한 칸은 예외
	if (board[markerPos] >0)
		if(markerPos !=32)
			return;

	board[originalPos]--;
	board[markerPos]++;
	int nSum = sum + boardScore[markerPos];
	map<int, int> nMarkerPoint = markerPoint;
	nMarkerPoint[checkMarker] = markerPos;
	
	//dfs ㄱㄱ
	for (int i = 1; i <= 4; i++)
	{
		//도착점에 있다면 고르지말자
		if (nMarkerPoint[i] == 32)
			continue;
		dfs(i, diceCnt + 1, nSum, nMarkerPoint);
	}
	board[originalPos]++;
	board[markerPos]--;
}

int main()
{
	map<int, int> markerPoint;
	for (int i = 1; i <= 4; i++)
		markerPoint[i] = 0;
	makeEdge();
	diceInput();

	for (int i = 1; i <= 4; i++)
		dfs(i, 0, 0, markerPoint);
	cout << result;
	return 0;
}

---

후기

처음보는 유형이라 엄청 당황했다.

하지만, 다풀고 나서 항상 하는 생각이지만 어려운 문제는 분명아니었다.

 

그리고 내 풀이는 dfs안에 map도 넣어놓고 완전탐색이고 해서 시간면에서 별로 좋은 풀이는 아닌듯 싶다.

시간을 줄이는 방법으로 완전탐색 말고 중복순열로 풀면 훨씬 시간을 줄일수 있을것 같은데 사실 어떻게 적용해야 할지 잘모르겠다. 이 문제는 다시 한번 풀 생각이라 다시 풀때는 중복순열로 한번 풀어봐야겠다.