[백준] 17825 주사위 윷놀이 - 그래프(Graph) + 브루트포스(Brute Force) + 중복순열 ( permutation with repetition ) JAVA

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

17825번: 주사위 윷놀이

코드설명

시뮬레이션 구현 그래프 문제입니다.

 

이 문제에서는 크게

1. 윷놀이판을 그래프로 만드는 것

2. 중복조합을 활용하여 윳놀이를 던지는것

 

위의 2가지 Step으로 나뉩니다.

윷놀이판 같은경우 그래프로 나누어도되고, 배열로 나누어도 되겠지만, 그래프로 나누는것이 매우 직관적입니다.

중복조합을 활용할떄 저 같은경우 주로 visited[] 를 활용하여 미리 10개의 순서에서 사용할 말을 정한뒤 진행하지만, 이번에는 중복조합에서 구해지는 즉시 진행함으로써 코드의 복잡도를 낮출 수 있었습니다.

 

이러한 문제같은경우 코드를 최대한 간단하게 짜는 방법을 생각해야하는것같습니다.

 

코드로직에 대해 좀 더 설명해보면,

1. 말 정보 세팅: 4개의 말이 게임 시작 노드(startNode)에 위치하고, 말은 현재 Node의 위치 정보를 가지고 있습니다.
2. 중복순열 계산: 재귀 함수 duplicatePermutation를 통해 10번의 주사위 던지기를 시뮬레이션합니다. 각 말은 주어진 주사위 값 만큼 이동하며, 도착한 최종노드에 따라 점수를 획득합니다. 중복순열을 통해 모든 경우의 수를 고려하며, 최종적으로 얻은 점수 중 최댓값을 찾습니다.
3. 말을 이동시킬때 : 말을 이동시키는 동안 문제에 주어진 규칙에 의해 움직입니다.
   1. 노드에 다른 말이 이미 위치해 있다면 해당 이동은 불가능합니다.
   2. 또한, 마지막 노드에(이때 헷갈린점은 40번째 칸이 아니라 도착칸을 의미합니다.) 도착하면 말을 종료시켜 더 이상 이동하지 않습니다.
4. Node 및 Horse 클래스:
   1. 각 노드는 점수와 다음 노드에 대한 참조, 현재 노드에 위치한 말을 저장합니다.
   2. 말은 현재 위치 정보를 Node Class의 참조정보로 가지고있고, 종료 여부를 가지고 있습니다.

 

문제에서 놓쳤었던 부분은, 말이 이동하면 그 이전 위치는 비어진다는 점입니다.

말이 이동하면, 이전 윷놀이 칸의 horseFlag가 false로 바뀌고 새롭게 이동할 칸이 horseFlag가 true로 바뀝니다.

완전탐색 이후에는, 다시 이전 윷놀이 칸의 horseFlag가 true로 바뀌고, 새롭게 이동할 칸의 horseFlag가 false 로 바뀝니다.

위의 로직을 놓쳤기에, 한번이라도 지나간 칸을 다시는 못지나가는 오류가 생겼었습니다.

코드

불필요한 메모리를 사용하지 않는 코드입니다.

속도는 아래의 코드와 비슷합니다.

 

아래의 코드와 차이점은, connect 함수가 시작점과 끝점을 바로 선언하고 들어갔기에 불필요한 로직이 사라집니다.

또한, 40번쨰 윷놀이판에서 처음에는 중복되는 부분을 따로 40 으로 선언하여 처리하였지만, 이 코드에서는 선언시 마지막 위치가 자동으로 40번쨰에 위치하므로 해당 코드로 connect를 진행하여 불필요한 메모리가 소요되지 않았습니다.

 

가장 큰 차이점은, 맨 하단의 코드는 푸른색 연결점인과 빨간색 연결점을 따로 분기하여 이동처리했지만,

아래의 코드는 푸른색인지, 빨간색인지 상관쓰지 않고 이동처리하였습니다.

그를 위해서 move==0, 첫 이동일경우에만 고려하도록 하여 코드양을 줄였습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	public static int N, M, K;
	public static int answer = 0;
	public static int[] arr;
	public static Node startNode = new Node(0), endNode = new Node(0);
	public static Node crossNode = new Node(25);
	public static Horse[] horse = new Horse[4];
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	//게임판을 생성합니다.
    	Node temp = startNode;
    	for(int i=2;i<=40;i+=2) {
    		temp.redNext = new Node(i);
    		if(i == 12) {
    			temp.blueNext = new Node(13);
    			connect(temp.blueNext, crossNode, 3, 2);
    		}else if(i == 22) {
    			temp.blueNext = new Node(22);
    			connect(temp.blueNext, crossNode, 2, 1);
    		}else if(i == 32) {
    			temp.blueNext = new Node(28);
    			connect(temp.blueNext, crossNode, -1, 2);
    		}
    		temp = temp.redNext;
    	}
    	connect(crossNode, temp, 5, 2);
    	temp.redNext = endNode;
    	
    	
    	//주사위 값 입력
    	arr = new int[10];
    	for(int i=0;i<10;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	//말 정보 세팅
    	for(int i=0;i<4;i++) {
    		horse[i] = new Horse(false, startNode);
    	}
    	
    	duplicatePermutation(0, 0);
    	System.out.println(answer);
	}
	
	public static void duplicatePermutation(int level, int score) {
		if(level == 10) {
			answer = Math.max(answer, score);
			return ;
		}
		
		//4개의 말에서 중복순열을 구할것입니다. 0번째 말이 10번 이동할수 있다는 의미입니다.  
		for(int i=0;i<4;i++) {
			
			//말 선택할시에는 이미 도착지점한 말은 선택하지않음.
			Horse h = horse[i];
			if(h.isDone == true) { //이미 완료된 말일경우 continue
				continue;
			}
			
			//갈수있는지 확인합니다.
			int dice = arr[level];
			Node movingNode = h.node; //현재 말의 위치를 이동시킬 것 입니다.
			for(int move=0; move<dice; move++) {
				if(move ==0 && movingNode.blueNext != null) { //처음출발한다면 blue인지 red인지 판단해야합니다.
					movingNode = movingNode.blueNext;
				}else {
					movingNode = movingNode.redNext;
				}
				if(movingNode.equals(endNode)) { //만약 종료지점이라면 더 이동할 수 있더라도 말을 중단시킵니다.
					break;
				}
			} //
			if(movingNode != endNode && movingNode.horse != null) { //만약 도착한 윳자리가 endNode가 아니면서 이미 다른노드가 존재한다면 이동하지 못하므로 중단합니다.
				continue;
			}
			
			//말이 끝자리에 도착했는지 확인합니다.
			boolean isDoneTemp = h.isDone;
			if(movingNode.equals(endNode)) { //만약끝자리라면 해당말을 종료시킵니다.
				h.isDone = true;
			}
			
			Node beforePositon = h.node;
			beforePositon.horse = null;
			movingNode.horse = h;
			h.node = movingNode;
			
			duplicatePermutation(level + 1, score + h.node.score);
		
			h.isDone = isDoneTemp;
			h.node = beforePositon;
			beforePositon.horse = h;
			movingNode.horse = null;
		}
		
	}
	
	public static void connect(Node startNode, Node endNode, int step, int count) {
		for(int i=0;i<count;i++) {
			startNode.redNext = new Node(startNode.score + step);
			startNode = startNode.redNext;
		}
		startNode.redNext = endNode;
	}
	
}

class Node{
	int score;
	Node redNext;
	Node blueNext;
	Horse horse;
	
	public Node(int score) {
		this.score = score;
	}
}

class Horse{
	boolean isDone;
	Node node;
	public Horse(boolean isDone, Node node) {
		this.isDone = isDone;
		this.node = node;
	}
}

 

 

투박하게 풀어본 코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int N,M, K;
	public static Node start = new Node(0);
	public static Node End = new Node(0);
	public static Node cross = new Node(25);
	public static Node fourty = new Node(40);
	public static Horse[] horseArray = new Horse[4];
	public static int[] diceArray = new int[10];
	public static int answer = 0;
	public static int maxAnswer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	for(int i=0;i<10;i++) {
    		diceArray[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	//우선 말을 두는 것은 중복순열로 처리한다.
    	//다만 중복순열로 처리하면서 말을 둘 수 있는지 없는지는 상태에 따라 다를 것 이다.
    	for(int i=0; i<4;i++) {
    		horseArray[i] = new Horse(i, start);
    	}
    	
    	
    	//문제의 조건을 보면, 빨간색 같은경우 2부터 40까지 먼저 증가하는 추세가 보인다.
    	Node temp = start;
    	for(int i = 2; i<=38; i += 2) {
    		temp.redNext = new Node(i);
    		temp.blueNext = null;
    		
    		//12를 연결할경우, temp는 10 입니다.
    		//10 에서는 blueNext로 13을 연결하고, 13에 16 19 25 를 이어서 연결합니다.
    		if( i == 12) {
    			temp.blueNext = new Node(13);
    			connectNode(temp.blueNext, 16, 3, 2, false);
    		}
    		
    		else if( i == 22) {
    			temp.blueNext = new Node(22);
    			connectNode(temp.blueNext, 24, 2, 1, false);
    		}
    		
    		else if( i == 32) {
    			temp.blueNext = new Node(28);
    			connectNode(temp.blueNext, 27, -1, 2, false);
    		}
    		temp = temp.redNext;
    		
			//만약 40인경우 42까지 처리하기 위함입니다.
    		if(i == 38) {
    			temp.redNext = fourty;
    			fourty.redNext = End;
    		}
    	}
    	
    	//교차로는 따로 연결해주었습니다.
    	Node crossTemp = cross;
    	connectNode(crossTemp, 30, 5, 2, true);
    	
    	simulate(0);
    	System.out.println(maxAnswer);
    	
    }
    
    //이제 말을 실제로 두는 작업을 진행할 것 입니다.
    //말을 두는 과정은 해당 말이 끝나지 않았다면, 여러번 두어도되는 중복순열의 방식입니다.
    //level은 주사위를 던진 횟수입니다.
    public static void simulate(int level) {
    	if(level == 10) {
    		maxAnswer = Math.max(maxAnswer, answer);
    		return ;
    	}
    	
    	//말을 보낼 것 입니다.
    	for(int kind=0;kind<4;kind++) {
    		Horse nowHorse = horseArray[kind];
    		Horse storeHorse = new Horse(nowHorse.num, nowHorse.currentNode);
    		
    		//만약 이미 도착한 상태라면 무시합니다.
    		if(nowHorse.currentNode == End) {
    			continue;
    		}
    		
    		//diceCnt만큼 말을 이동시켜줄 것 입니다.
    		int diceCnt = diceArray[level];
    		
    		//만약 현재 말의 위치에서 파란색 칸이 존재한다면, 파란색칸의 방향으로 먼저 이동합니다.
    		if(nowHorse.currentNode.blueNext != null) {
    			nowHorse.currentNode = nowHorse.currentNode.blueNext;
    			diceCnt -= 1;
    			//파란색칸은 5가 나오더라도 도착할 가능성 없음.
    			for(int moveCnt = 0; moveCnt<diceCnt; moveCnt++) {
        			nowHorse.currentNode = nowHorse.currentNode.redNext;
        		}
    			
    			//도착칸에 말이 없어야만 합니다.
    			if(nowHorse.currentNode.horseFlag == false) {
    				storeHorse.currentNode.horseFlag = false;
    				
    				answer += nowHorse.currentNode.num;
    				nowHorse.currentNode.horseFlag = true;
    				simulate(level + 1);
    				answer -= nowHorse.currentNode.num;
    				nowHorse.currentNode.horseFlag = false;
    				
    				storeHorse.currentNode.horseFlag = true;
    			}
				//원상복구
    			nowHorse.currentNode = storeHorse.currentNode;
				nowHorse.num = storeHorse.num;

    		}
    		
    		//만약 현재 말의 위치에서 파란색 칸이 없고, 빨간색칸만 존재한다면, 빨간색칸의 방향으로 먼저 이동합니다.
    		else if(nowHorse.currentNode.redNext != null) {
    			for(int moveCnt = 0; moveCnt<diceCnt; moveCnt++) {
    				if(nowHorse.currentNode == End) {
    					break;
    				}
        			nowHorse.currentNode = nowHorse.currentNode.redNext;
        		}
    			//만약, 말의 이동을 마치는 칸이 도착칸이 아니면서, 다른 말이 있으면 그 말은 고를 수 없으므로 원상복구 시킵니다.
    			if(nowHorse.currentNode.horseFlag == false || nowHorse.currentNode == End) {
    				//말을 이동하도록 처리할 것이니 현재말의 위치에 사라짐 처리해줍니다.
    				storeHorse.currentNode.horseFlag = false;
    				
    				answer += nowHorse.currentNode.num;
    				nowHorse.currentNode.horseFlag = true;
    				simulate(level + 1);
    				answer -= nowHorse.currentNode.num;
    				nowHorse.currentNode.horseFlag = false;

    				//말을 이동하도록 처리할 것이니 다시 돌아온 원래 말의 위치에 도착처리합니다.
    				storeHorse.currentNode.horseFlag = true;
    			}
    			nowHorse.currentNode = storeHorse.currentNode;
				nowHorse.num = storeHorse.num;
    		}
    		
    	}
    	
    	
    	
    }
    
    public static void connectNode(Node node, int start, int interval, int repeatCount, boolean crossFlag) {
    	int num = start;
    	for(int i=0;i<repeatCount; i++) {
    		node.redNext = new Node(num);
    		node = node.redNext;
    		num += interval;
    	}

    	//만약 crossFlag가 false라면 마지막에는 25를 연결해주자.
    	if(crossFlag == false) {
        	node.redNext = cross;    		
    	}
    	
    	//만약 crossFlag == true라면, 마지막에는 40을 연결해주자.
    	else if(crossFlag == true) {
    		node.redNext = fourty;
    	}
    	
    }
    
    public static void print() {
    	//잘연결되었는지 확인하자.
    	Node printTemp = start;
    	while(printTemp != null) {
    		System.out.println(printTemp.num);
    		
    		if(printTemp.blueNext != null) {
    			System.out.println("--------Start---------");
    			Node newPrintTemp = printTemp.blueNext;
    			while(newPrintTemp != null) {
    				System.out.println(newPrintTemp.num);
    				newPrintTemp = newPrintTemp.redNext;
    			}
    			System.out.println("-----End--------");
    		}
    		
    		printTemp = printTemp.redNext;
    	}
    	
    }
    
}

class Horse{
	int num;
	Node currentNode = null;
	public Horse(int num, Node currentNode) {
		this.num = num;
		this.currentNode = currentNode;
	}
}

class Node{
	int num;
	Node redNext = null;
	Node blueNext = null;
	boolean horseFlag = false;
	public Node(int num) {
		this.num = num;	
	}
	
}