[C++] 백준(BOJ) - 17825 : 주사위 윷놀이

19 Mar 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 17825 : 주사위 윷놀이(링크)

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

알고리즘

1. 구현
2. 브루트포스
3. 백트래킹

풀이

• 맵을 구현
  • 빨간색 라인을 0번째 인덱스에, 파란색 라인을 1번째 인덱스에 넣는 아이디어
• 완전탐색
  • 말 4개를 방문처리 체크 해제하며 완전탐색

코드

// BOJ-17825 : 주사위 윷놀이
#include <bits/stdc++.h>
using namespace std;

int n = 10, a[14], hor[4];
int v[104];
vector<int> adj[54];

void add(int here, int there)
{
	adj[here].push_back(there);
}

void setMap()
{
	for (int i = 0; i <= 19; i++) add(i, i + 1);
	add(5, 21); add(21, 22); add(22, 23); add(23, 24);
	add(10, 27); add(27, 28); add(28, 24); add(24, 25);
	add(15, 29); add(29, 30); add(30, 31); add(31, 24);
	add(25, 26); add(26, 20); add(20, 100);

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

bool isHor(int hor_idx, int idx)
{
	if (hor_idx == 100) return false;
	for (int i = 0; i < 4; i++)
	{
		if (i == idx) continue;
		if (hor[i] == hor_idx) return true;
	}
	return false;
}

int move(int here, int cnt)
{
	if (here == 100) return 100; // 도착한 경우 리턴 (도착 지점의 idx값 100으로 지정)
	
	// 파란화살표 강제이동
	if (adj[here].size() >= 2)
	{
		here = adj[here][1];
		cnt--;
	}

	if (cnt) {
		queue<int> q;
		q.push(here);
		int there;
		while (q.size())
		{
			int x = q.front();
			q.pop();
			there = adj[x][0];
			q.push(there);
			if (there == 100) break;
			cnt--;
			if (cnt == 0) break;
		}
		return there;
	}
	else return here;
}

// 완전 탐색
int go(int here)
{
	if (here == n) return 0; // 10개의 턴 모두 사용 -> 리턴
	int res = 0;

	for (int i = 0; i < 4; i++)
	{
		int tmp_idx = hor[i]; // 각각의 말 임시 위치 저장
		int hor_idx = move(tmp_idx, a[here]); // 각각 말 a[here]만큼 움직이는 로직
		if (isHor(hor_idx, i)) continue; // 움직일 위치가 비어있는지 확인하는 로직
		
		// 완전탐색의 기본 꼴
		hor[i] = hor_idx;
		res = max(res, go(here + 1) + v[hor_idx]);
		hor[i] = tmp_idx;
	}
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	setMap();

	for (int i = 0; i < n; i++) cin >> a[i];

	cout << go(0) << '\n';

	return 0;
}

평가

• 정렬과 라인스위핑은 세트로 생각
• idx 기반 탐색
• 시작 지점 기준으로 나눠서 생각하기 (케이스 바이 케이스 따져 나가기)