17825 주사위 윷놀이 : https://www.acmicpc.net/problem/17825
Problem
Solve
게임판을 만드는게 핵심이였던 이번 문제.
게임판을 만드는데도 메인 길(둘러서 가는길)과 지름길(가운데 길)로 가는 칸의 숫자가 중복되는게 있어서 조금 까다로웠었다.
게임판은 트리처럼 구현해서 출발지점(root)를 만들고 메인 길을 만들고 그 중 10번, 20번, 30번 Node에 지름길 Node를 만들어서 이동하게 했다.
이때 조심해야할 것은 해당 Node에 말이 있는지 여부를 확인하는데 여부를 확인하기 위해서는 25번부터 35번 Node는 지름길을 이용하는 Node들이 공통으로 가져야하고 40번 노드는 메인 길과 지름길로 가는 모든 Node가 공통으로 가져야 한다는 것이다.
게임판을 만들었다면 어떤 말을 주어진 주사위 숫자에 맞게 이동시킬것인지 백트래킹을 통해 생성하고 해당 주사위 숫자에 맞게 주어진 말이 이동하여 이동하려는 Node에 말이 있는지 여부 확인과 이미 도착한 말인지를 확인하면서 방문했던 Node의 숫자의 합을 구하여 그 최댓값을 구한다.
코드에 자세하게 주석을 달아놨다.
풀었던 문제중에 가장 오래걸렸던 문제.
첫번째 풀었을때는 백트래킹으로 이동시킬 말을 선택하는 것이 생각대로 구현이 잘 안됬고,
두번째 풀었을때는 테스트 케이스 3번을 해결못해서 이틀 걸려 풀었다.
https://www.acmicpc.net/board/view/62510 이 질문 덕분에 겨우 해결할수 있었다ㅠㅜ
(위에 설명했던 공통으로 가져야할 Node에서 40번 노드가 지름길로 갔을때 40번과 메인길로 갔을때 40번 Node가 달랐다)
Code
public class 주사위윷놀이 {
static LinkedList<Node> board;
static int[] numbers;
static int answer;
static Node root;
static int[] orders;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//주어진 10개의 주사위 번호
numbers = new int[10];
//10개의 주사위 번호에 맞게 움직일 말들(각 index에 말 번호)
orders = new int[10];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < 10; i++) {
numbers[i] = Integer.parseInt(st.nextToken());
}
//게임판 생성
setBoard();
//각 주사위 번호에 말 번호 생성
permutation(0);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
//각 주사위 번호의 말 순서
static void permutation(int depth) {
//10개의 주사위 번호에 말을 생성했다면 주사위 번호에 맞게 말들 움직이기
//방문했던 Node의 번호 합 반환
if (depth >= 10) {
answer = Math.max(answer, play());
return;
}
//각 주사위 번호에 말 생성
for (int i = 0; i < 4; i++) {
orders[depth] = i;
permutation(depth + 1);
}
}
//말 이동시키기
static int play() {
int sum=0;
//말이 지름길로 이동하는지 메인길로 이동하는지
//true : 메인길, false : 지름길
boolean[] status = new boolean[4];
//각 말이 위치한 Node
Node[] horses = new Node[4];
for (int i = 0; i < 4; i++) {
horses[i] = root;
status[i] = true;
}
//주어진 주사위 숫자만큼 해당 말 이동
for (int i = 0; i < 10; i++) {
//이동할 말
int currentHours = orders[i];
//이동할 거리
int move = numbers[i];
//이동할 말의 현재 Node
Node current = horses[currentHours];
//이동 후 말의 Node
Node moveResult;
//현재 말이 위치한 Node가 10,20,30중 하나라면 지름길로 이동해야한다.
if (current.number == 10 || current.number == 20 || current.number == 30) {
moveResult = current.moveNode(move, false);
//한번 지름길로 이동하면 계속 지름길로 이동
status[currentHours] = false;
} else {
moveResult = current.moveNode(move, status[currentHours]);
}
//이동하여 도착한 Node가 도착한 곳이라면 이전에 있던 Node에 방문상태를 지워주고 끝.
if (moveResult == null) {
current.isVisit = false;
continue;
}
//이동하여 도착한 Node에 이미 말이 존재한다면 해당 주사위에 주어진 말들은 더 이상 이동할수 없으므로 함수 종료
else if (moveResult.isVisit) {
sum = 0;
break;
}
//다음 Node로 이동하면 이전에 있던 Node에 방문상태 false, 이동한 Node에 방문상태 true
//이동한 Node의 번호 더해주기
//해당 말을 이동한 Node로 갱신
else {
current.isVisit = false;
moveResult.isVisit = true;
sum += moveResult.number;
horses[currentHours] = moveResult;
}
}
//모든 말의 이동이 완료되었거나 중간에 종료가 되었다면 다음 함수가 사용할수 있도록 현재 말들이 있는 Node의 방문여부를 false로 초기화 해준다.
for(int i=0;i<4;i++){
horses[i].isVisit = false;
}
return sum;
}
//게임판 생성
static void setBoard() {
board = new LinkedList<>();
int num = 0;
root = new Node(0);
//지름길로 이동하면 25번, 30번, 35번, 40번이 공통으로 사용된다.
Node center = new Node(25);
Node temp = center;
Node last;
num = 25;
for (int i = 0; i < 3; i++) {
num += 5;
temp.addSubNode(new Node(num));
temp = temp.subNext;
}
//지름길과 메인길에서 공통으로 사용하는 40번 노드를 메인길 생성할때 사용하기 위해 따로 빼놓는다.
last = temp;
Node start = root;
num = 0;
//메인길생성
//마지막 40번 노드는 뺴놓고 생성하기 위해 마지막은 반복은 제외한다.
for (int i = 0; i <19; i++) {
//5번 Node일때 13,16,19 노드를 10번 노드의 subNext에 저장
if (i == 5) {
Node sub = start;
for (int j = 1; j <= 3; j++) {
sub.addSubNode(new Node(num + (j * 3)));
sub = sub.subNext;
}
//19번 노드의 subNext에 25번 Node 추가
sub.addSubNode(center);
}
//20번 Node일 때 22,24번 Node에 25번 Node 추가
else if (i == 10) {
Node sub = start;
for (int j = 1; j <= 2; j++) {
sub.addSubNode(new Node(num + (j * 2)));
sub = sub.subNext;
}
//24번 노드의 subNext에 25번 Node 추가
sub.addSubNode(center);
}
//20번 Node일 때 28,27,26번 Node에 25번 Node 추가
else if (i == 15) {
Node sub = start;
int subNum = num - 1;
for (int j = 1; j <= 3; j++) {
sub.addSubNode(new Node(subNum - j));
sub = sub.subNext;
}
//26번 노드의 subNext에 25번 Node 추가
sub.addSubNode(center);
}
//메인길의 Node번호는 2씩 증가
num += 2;
//메인길은 Node의 mainNext에 저장
start.addNode(new Node(num));
start = start.mainNext;
}
//메인길의 마지막에 40번 Node추가
start.addNode(last);
}
static class Node {
int number;
Node mainNext;
Node subNext;
boolean isVisit;
public Node(int number) {
this.number = number;
this.isVisit = false;
}
//메인길로 이동하는 다음 Node 추가
public void addNode(Node mainNext) {
this.mainNext = mainNext;
}
//지름길로 이동하는 다음 Node 추가
public void addSubNode(Node subNext) {
this.subNext = subNext;
}
//move : 이동 거리, isMain : 메인길인지 지름길인지 여부
public Node moveNode(int move, boolean isMain) {
Node node = this;
while (move-- > 0) {
//메인길로 이동한다면 mainNext의 Node방문
if (isMain) {
node = node.mainNext;
}
//지름길로 이동한다면 subNext의 Node방문
else {
node = node.subNext;
}
//이동한 Node가 null이라면 도착한것이므로 null반환
if (node == null)
return null;
}
return node;
}
}
}
Result
시간도 오래걸리고 짜잘한 실수들을 찾지 못하니 멘탈도 많이 나갔던 문제였다.
아직 구현문제가 부족한듯싶다..
Reference
내 꿈은 좋은 개발자