[C++,구현, 중복 순열] 백준 17825번 주사위 윷놀이 문제풀이

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

17825번: 주사위 윷놀이

 

주사위 윷놀이, 구현에서도 어려운 축에 속한다고 생각한다.

 

주사위에서 나올 수 있는 10개의 수 순서에 각각 4개의 말들을 매칭 시킨다고 하면 중복 순열이다.

전체의 경우의 수는 4^10 가지가 나온다.

 

처음에는 아래와 같이 풀이하였다.

#include <iostream>
#include <vector>
using namespace std;

typedef struct lo
{
	int x, y;
};

int pan[4][30] = 
{ { -1, 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} };
int val[10];
int ans;
vector <lo> mal_lo(5); //말의 위치
int order[10];

bool is_full_mal(int i)
{
	int x = mal_lo[i].x;
	int y = mal_lo[i].y;
	int val = pan[x][y];
	for (int idx = 1; idx <= 4; idx++)
	{
		int idx_val = pan[mal_lo[idx].x][mal_lo[idx].y];
		if (idx == i) continue;
		if (idx_val != 0 && mal_lo[idx].x == x && mal_lo[idx].y == y) return true;
		if (idx_val != 0 && x > 1 && y > 2 && idx_val == val)return true;
		if (val == 40 && idx_val == val)return true;
	}
	return false;
}

void checkChange(int i)
{
	if (mal_lo[i].x == 0 && mal_lo[i].y == 5)
		mal_lo[i] = { 1, 0 };
	else if (mal_lo[i].x == 0 && mal_lo[i].y == 10)
		mal_lo[i] = { 2, 0 };
	else if (mal_lo[i].x == 0 && mal_lo[i].y == 15)
		mal_lo[i] = { 3, 0 };
	else if (mal_lo[i].x == 1 && mal_lo[i].y == 0)
		mal_lo[i] = { 0, 5 };
	else if (mal_lo[i].x == 2 && mal_lo[i].y == 0)
		mal_lo[i] = { 0, 10 };
	else if (mal_lo[i].x == 3 && mal_lo[i].y == 0)
		mal_lo[i] = { 0, 15 };
}

void print_order()
{
	for (int i = 0; i < 10; i++)
		cout << order[i] << " ";
	cout << "\n";
}


void pickMal(int d, int v)
{
	if (d == 10){
		if (ans <= v){
			print_order();
			ans = v;
		}
		return;
	}

	for (int i = 1; i <= 4; i++)
	{
		if (pan[mal_lo[i].x][mal_lo[i].y]==0)  continue;

		mal_lo[i].y += val[d];
		checkChange(i);

		if (is_full_mal(i)){
			checkChange(i);
			mal_lo[i].y -= val[d];
			continue;
		}
		order[d] = i;
		pickMal(d + 1, v + pan[mal_lo[i].x][mal_lo[i].y]);

		checkChange(i);
		mal_lo[i].y -= val[d];
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	for (int i = 0; i < 10; i++)
		cin >> val[i];

	pickMal(0, 0);
	cout << ans;
	return 0;
}

 

하지만 조금만 더 생각해보면 단순 중복순열은 아님을 알 수 있다. 

4^10개의 매칭에서 중복되는 패턴이 나온다.

즉, 4번 말을 처음 꺼내든 2번 말을 제일 처음 꺼내 든 말만 달라지고 패턴을 같은 패턴을 보였다.

아래는 백준의 1번 예제를 인풋으로 위 코드를 실행한 결과이다.

중복순열

 

위처럼 말만 달라지고 같은 패턴을 보이는 부분이 여러 개 존재한다.

당연히 결과도 20ms로 다른 분들에 비해 상대적으로 느렸다.

위처럼 말의 종류가 상관없을때 중복을 제거하는 방법은 없을까?

 

있더라.

#include <iostream>
#include <vector>
using namespace std;

typedef struct lo{
	int x, y;
}lo;


int val[10];
int map[4][30] = {
	{-1,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}
};
int ans;

vector <lo> mal;
int order[10];


void checkIdx(int idx)
{
	if (mal[idx].x == 0 && mal[idx].y == 5)
		mal[idx] = { 1, 0 };
	else if (mal[idx].x == 0 && mal[idx].y == 10)
		mal[idx] = { 2, 0 };
	else if (mal[idx].x == 0 && mal[idx].y == 15)
		mal[idx] = { 3, 0 };	
	else if (mal[idx].x == 1 && mal[idx].y == 0)
		mal[idx] = { 0, 5 };
	else if (mal[idx].x == 2 && mal[idx].y == 0)
		mal[idx] = { 0, 10 };
	else if (mal[idx].x == 3 && mal[idx].y == 0)
		mal[idx] = { 0, 15 };
}

bool check_overlap(int t)
{
	int tx = mal[t].x;
	int ty = mal[t].y;
	for (int i = 0; i < mal.size(); i++)
	{
		if (t == i || map[mal[i].x][mal[i].y] == 0)continue;
		int rx = mal[i].x;
		int ry = mal[i].y;
		if (tx == rx && ty == ry) return true;
		if (tx > 0 && ty > 2 && rx > 0 && ry > 2 && map[tx][ty] == map[rx][ry])return true;
		if (map[tx][ty] == 40 && map[tx][ty] == map[rx][ry])return true;
	}

	return false;
}

void print_order()
{
	for (int i = 0; i < 10; i++)
		cout << order[i] << " ";
	cout << "\n";
}

void pickMal(int d, int s)
{
	if (d == 10)
	{
		if (ans < s){
			print_order();
			ans = s;
		}
		return;
	}
	for (int i = 0; i < mal.size(); i++)
	{
		if (map[mal[i].x][mal[i].y] == 0)continue;

		mal[i].y += val[d];
		checkIdx(i);

		if (check_overlap(i)){
			checkIdx(i);
			mal[i].y -= val[d];
			continue;
		}
		order[d] = i;
		pickMal(d + 1, s + map[mal[i].x][mal[i].y]);

		checkIdx(i);
		mal[i].y -= val[d];
	}

	if (mal.size() < 4){
		int nidx = mal.size();
		mal.push_back({ 0, 0 });
		mal[nidx].y += val[d];
		checkIdx(nidx);
		if (!check_overlap(nidx)){
			order[d] = nidx;
			pickMal(d + 1, s + map[mal[nidx].x][mal[nidx].y]);
		}
		mal.pop_back();
	}

}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 0; i < 10; i++)
		cin >> val[i];

	pickMal(0,0);

	cout << ans;

	return 0;
}

위의 코드를 실행시키면 아래와 같이 나온다

각 말의 구분이 없는 중복순열

 

위의 코드와 비교해보면 확실히 한 패턴만 표현되는 것을 알 수 있다. 

핵심적인 차이는 dfs로 구현한 backtracking(pickMal() 함수) 부분에서 다음 노드로 넘어가는 부분이다.

for (int i = 1; i <= 4; i++) => for (int i = 0; i < mal.size(); i++)

모든 말을 대입하는 것 대신 지금 보드에 있는 말을 중심으로 backtracking을 수행하는 것이다. 

여기서 말을 추가하는 부분이 중요하다.

if (mal.size() < 4)
{
		int nidx = mal.size();
		mal.push_back({ 0, 0 });
		mal[nidx].y += val[d];
		checkIdx(nidx);
		if (!check_overlap(nidx)){
			order[d] = nidx+1;
			pickMal(d + 1, s + map[mal[nidx].x][mal[nidx].y]);
		}
		mal.pop_back();
}
    

새로운 말을 추가했을 때 문제에서 요구한 조건(말은 같은 위치에 놓일 수 없다.)에 걸리지 않는다면 다음 노드로 넘어가게 함으로써 각 노드마다 backtracking을 수행할 가지를 늘려주는 것이다.

 

이렇게 하면 "지금 보드에 있는 말을 움직일 것인가" "시작점에 있는 말을 새롭게 움직일 것인가"로 양분되고 보드에 있는 말은 또 따로 순열을 돌릴 수 있게 된다.

 

질문, 오류 수정이 환영합니다~^^