[BOJ 17825] 주사위 윷놀이
업데이트:
문제
- BOJ 17825
- 문제의 저작권은 Baekjoon Online Judge에 있습니다.
접근방식
조건이 굉장히 까다롭고 헷갈리는 문제이다.
며칠동안 고민하다가 도저히 해결책이 떠오르지 않아 여러 코드를 참고할 수 밖에 없었다.
배열, 링크드리스트로 푸는 방법 중 다음으로 이동할 방향이 정해져 있기 때문에 링크드리스트로 풀었다.
풀이 순서는 다음과 같다.
- 윷놀이 시작 전 윷놀이판을 세운다 =>
init()호출 윷놀이판은 크게 1)바깥 경로, 2. 파란 위치로 가는 방법 두가지가 있다.
바깥 경로는 파란 위치를 따라가지 않고 오로지 빨간 선만을 따라 도착하는 경우이다.
이를 구분짓기 위해 각각의 윷놀이판을Node객체로 생성한다.
static class Node{//윷놀이판
int score; //점수
boolean isEmpty; //다른 말이 이미 와있는지
boolean isFinish; //도착했는지
Node next; //다음 노드
Node fast; //지름길
public Node(int score){
this.score = score;
this.isEmpty = true;
this.isFinish = false;
}
public Node addNext(int score){ //노드 연결
Node nextNode = new Node(score);
this.next = nextNode;
return nextNode;
}
public static Node getNode(Node start, int score){ //start를 시작지점으로 점수가 score인 노드 찾기
Node tmp = start.next;
while(true){
if(tmp.score == score) return tmp;
tmp = tmp.next;
}
}
}
디폴트 경로를 바깥 경로로 생각하고, 파란 위치 즉 지름길이 있는 노드(10, 20, 25, 30)일 경우에만 fast멤버변수에 파란 방향으로 가서 도착할 다음 노드를 가리켜준다.
이렇게 특수한 경우를 제외하고는 현재 노드의 next멤버변수에 빨간 방향으로 가서 도착할 다음 노드를 가리켜준다.
private static void init() {
start = new Node(0); //시작
Node tmp = start;
//i. 바깥 경로 설정
for(int i=2; i<=40; i+=2) tmp = tmp.addNext(i);
Node end = tmp.addNext(0); //도착
end.isFinish = true;
end.next = end;
Node center = new Node(25);
//ii. 교차점(10,20,30,25)일때 경로 설정
//교차점 10-13-16-19-25
tmp = Node.getNode(start, 10);
tmp = tmp.fast = new Node(13);
tmp = tmp.addNext(16);
tmp = tmp.addNext(19);
tmp.next = center;
//교차점 20-22-24-25
tmp = Node.getNode(start, 20);
tmp = tmp.fast = new Node(22);
tmp = tmp.addNext(24);
tmp.next = center;
//교차점 30-28-27-26-25
tmp = Node.getNode(start, 30);
tmp = tmp.fast = new Node(28);
tmp = tmp.addNext(27);
tmp = tmp.addNext(26);
tmp.next = center;
//교차점 25-30-35-40-도착
tmp = center.addNext(30);
tmp = tmp.addNext(35);
tmp.next = Node.getNode(start, 40); //바깥경로와 연결
}
- 4개의 말을 중복해서 10번 줄세운다 => 중복순열(4Π10)
중복순열로4x4x....x4를 10번 곱하면1,048,576연산이 필요하다. 1억번 연산을 해야 1초가 지나므로 제한 시간에 충분하므로 가지치기없이 전체 경우의 수를 따져도 된다.
각각 만들어진 경우의 수를 가지고 윷놀이를 시작한다 =>go()호출
private static void per(int cnt){
if(cnt==11){
go(); //3. 윷놀이 시작
return;
}
for(int i=1; i<=4; i++){
order[cnt] = i;
per(cnt+1);
}
}
- 윷놀이를 시작한다.
3-1. 뽑은 순서대로 현재 말을 선택한다.
3-2. 주사위수만큼 말을 이동한다.
1) 처음 이동 위치가 파란색이면 파란 방향으로 간다.
2). 1)가 아니면 파란 방향으로 간다.
3-3. 모든 이동 후 도착한 노드에 다른 말이 있는지 체크한다.
1) 다른 말이 있으면 점수를 무효처리시키고 게임을 종료한다.
2) 비었다면 현재 위치에 말이 왔음을 표시한다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
static Node[] horses; //말 1234
static int[] dices; //주사위
static int[] order; //말 순서
static boolean[] visited; //선택됐는지
static int Ans; //최대 점수
static Node start; //시작 지점
static class Node{//윷놀이판
int score; //점수
boolean isEmpty; //다른 말이 이미 와있는지
boolean isFinish; //도착했는지
Node next; //빨간 방향으로 오는 노드(default)
Node fast; //파란 방향으로 오는 노드
public Node(int score){
this.score = score;
this.isEmpty = true;
this.isFinish = false;
}
public Node addNext(int score){ //노드 연결
Node nextNode = new Node(score);
this.next = nextNode;
return nextNode;
}
public static Node getNode(Node start, int score){ //start를 시작지점으로 점수가 score인 노드 찾기
Node tmp = start.next;
while(true){
if(tmp.score == score) return tmp;
tmp = tmp.next;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
dices = new int[11];
horses = new Node[5]; //1부터
order = new int[11]; //1부터
visited = new boolean[5];
for(int i=1; i<=10; i++) dices[i] = Integer.parseInt(st.nextToken());
//1. 윷놀이판 만들기
init();
//2. 말 순서 구하기: 4Π10 중복순열
per(1);
System.out.println(Ans);
}
private static void init() {
start = new Node(0); //시작
Node tmp = start;
//i. 바깥 경로 설정
for(int i=2; i<=40; i+=2) tmp = tmp.addNext(i);
Node end = tmp.addNext(0); //도착
end.isFinish = true;
end.next = end;
Node center = new Node(25);
//ii. 교차점(10,20,30,25)일때 경로 설정
//교차점 10-13-16-19-25
tmp = Node.getNode(start, 10);
tmp = tmp.fast = new Node(13);
tmp = tmp.addNext(16);
tmp = tmp.addNext(19);
tmp.next = center;
//교차점 20-22-24-25
tmp = Node.getNode(start, 20);
tmp = tmp.fast = new Node(22);
tmp = tmp.addNext(24);
tmp.next = center;
//교차점 30-28-27-26-25
tmp = Node.getNode(start, 30);
tmp = tmp.fast = new Node(28);
tmp = tmp.addNext(27);
tmp = tmp.addNext(26);
tmp.next = center;
//교차점 25-30-35-40-도착
tmp = center.addNext(30);
tmp = tmp.addNext(35);
tmp.next = Node.getNode(start, 40); //바깥경로와 연결
}
private static void per(int cnt){
if(cnt==11){
go(); //3. 윷놀이 시작
return;
}
for(int i=1; i<=4; i++){
order[cnt] = i;
per(cnt+1);
}
}
private static void go() {
Arrays.fill(horses, start); //모든 말 시작지점으로 셋팅
int total=0; //게임진행으로 얻은 점수
for(int i=1; i<=10; i++){
Node now = horses[order[i]]; //현재 턴에서 말 선택
now.isEmpty = true;
for(int j=1; j<=dices[i]; j++){ //주사위 점수만큼 이동
//처음 이동 위치가 파란색이면
if(j==1 && now.fast != null) now = now.fast;
else now = now.next;
}//End 이동
//이동 후 다른말이 있는지 체크
if(!now.isEmpty && !now.isFinish){
break;
}else{
now.isEmpty = false; //현재 위치에 말 있음 표시
total += now.score;
horses[order[i]] = now;
}
}//End 게임
//말 초기화
for(int i=1; i<=4; i++) horses[i].isEmpty = true;
Ans = Math.max(Ans, total);
}
}