[ Baekjoon ] 17825. 주사위 윷놀이

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

17825번: 주사위 윷놀이

풀이 방법

route 배열

게임판을 저장하기 위해서 위와 같이 5개의 경로를 나누어 각 배열에 저장했다. 각 칸에 적혀진 값을 순서대로 저장한다.

struct board {
	int route[21] = { -1, }; // on_route = 0
	int route10[4] = { 10, 13, 16, 19 }; // on_route = 1
	int route20[3] = { 20, 22, 24 }; // on_route = 2
	int route30[4] = { 30, 28, 27, 26 }; // on_route = 3
	int route25[3] = { 25, 30, 35 }; // on_route = 4
	board() {
		for (int i = 1; i <= 20; i++) {
			route[i] = i * 2;
		}
	}
} game_board;

 

말의 상태, 정보, 움직임 등을 나타내기 위해 horse라는 구조체를 다음과 같이 정의했다.

struct horse {
	int on_route;
	int pos;
	int id;
	bool finish;

	horse(int id_) : on_route(0), pos(0), id(id_), finish(false){};
	int move_forward(int move_cnt);
	void move_backward();
    
private:
	stack < pair<int, int> > passby; // (prev on_route, prev pos)
};

on_route은 위에서 정의한 5개의 경로 중 어느 경로 상에 존재하는지를 저장하고, pos는 해당 경로 내에서 몇번째 위치에 있는지를 나타낸다. id는 말끼리 구분하기 위해 고유한 값을 가진다. 그리고 finish는 말이 도착칸에 도착하면 true로 설정된다. 마지막으로 passby는 해당 말이 지나온 경로를 저장하여 완전 탐색 시 움직이기 전의 상태로 복구할 때에 사용한다.

 

move_forward() 함수는 인자로 주어진 값만큼 해당 말을 움직이고 움직인 칸의 값을 반환하는 함수이다. 만약 도착칸에 도착했다면 0을 반환한다. 특별한 알고리즘은 없고, 하드코딩했다.

 

move_backward() 함수는 가장 최근에 머물렀던 칸으로 다시 돌아가는 함수이다. 스택을 이용해서 손쉽게 구현했다.

int horse::move_backward() {
	finish = false;
	tie(on_route, pos) = passby.top();
	passby.pop();
}

 

전체 코드는 여기서 확인할 수 있다.