BOJ - 주사위 윷놀이 17825번 (python, JAVA)

❓ 문제 - 백준 주사위 윷놀이 17825번 - python, JAVA 풀이법

 

출처 

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

17825번: 주사위 윷놀이

 

 

📝 문제해결법

1. 이 문제는 구현+BFS(중복순열)로 풀었다.

• 일단 게임판의 인덱스로 다음 연결되는 인덱스의 정보를 connect 리스트에 저장한다.
• 1 ~ 20은 시작부터 도착 전까지 외곽지역을 나타내며, 21은 도착인데 자기 자신을 가리키게 저장한다. 또한 22 ~ 24는 10 점의 파란색 안쪽의 지역을 인덱스로 나타내고, 25 ~ 26은 20점 안쪽의 지역을 나타내고, 27 ~ 29는 30점 안쪽의 지역을 인덱스로 나타낸다. 또한 30 ~ 32는 가운데 25점 부터 40점 전까지의 지역을 나타내는 인덱스이다.
• board 리스트를 통해 각 지역 인덱스에 속한 점수들을 나타낸다.
• dul 리스트로 각 지역마다 말이 존재하는지 존재하지 않는지를 나타낸다.
• DFS(중복순열)을 돌려 4**10 가지 경우를 다 탐색하여 어떤 말을 10번 골랐을 때 최대 점수를 얻을 수 있는지 최대값을 계속 갱신해서 정답을 출력한다.

2. BFS(중복순열)로 풀었다.

• depth로 말을 고른 횟수를 나타내며 총 10번 말을 골랐을 때 지금까지 얻었던 점수와 현재까지 최대 점수를 비교해서 최대값으로 갱신한 후 리턴한다.
• 4가지 말에 대해서 모두 다 탐색할 수 있도록 하는데, 고른 말의 현재 위치에서 주사위만큼을 이동시킨 후, 이동시킨 지역이 만약 도착지역이 아니면서 말이 이미 존재한다면 그 말을 고르는 것을 취소한다.
• 고른 말의 현재 위치에서 주사위만큼 이동시키는 방법은 만약 말의 현재 위치가 5, 10, 15번 인덱스(파란지역이여서 방향을 변경하는 곳)이면 해당 지역 다음을 가리키는 곳으로 인덱스를 변경해준다. 그 후 이동시켰으므로 이동해야하는 주사위의 값을 -1 해준다.
• 그리고 현재 위치에서 말을 이동시켰을 때도 외곽 지역이라면 이동시킬 만큼만 더해서 이동 위치의 인덱스를 구하고, 만약 현재 위치가 파란색 지역에서 시작했을 때는 connect 리스트를 활용하여 다음 이동 위치의 인덱스를 구한다.
• 그 말을 골랐다고 했을 때, 현재 위치의 말이 존재하지 않음으로, 이동될 지역에 말이 존재함으로, 현재 말의 위치 정보를 담은 리스트를 변경한다. 이동시킨 후의 위치에 해당하는 점수를 더하고 depth +1 해준 후 dfs를 호출한다. 

3. 문제 풀면서 느낀점

• 각 지역을 다음 연결될 인덱스를 리스트에 저장하여 연결시킨다는 점이 특이했다. 이런 방법도 기억해놔야겠다.

 

💻 소스코드 (python)

# 주사위 윷놀이 - BOJ 17825
# BFS + 구현
dice = list(map(int, input().split()))

horse = [0, 0, 0, 0]

connet = [0 for _ in range(33)]
# 외곽(1 ~ 20)
for i in range(21):
    connet[i] = i+1
# 도착
connet[21] = 21
# 10번 다음 (22 ~ 24)
connet[22], connet[23], connet[24] = 23, 24, 30
# 20번 다음 (25 ~ 26)
connet[25], connet[26] = 26, 30
# 30번 다음 (27 ~ 29)
connet[27], connet[28], connet[29] = 28, 29, 30
# 가운데(25) ~ 40전
connet[30], connet[31], connet[32] = 31, 32, 20

# 점수
board = [0 for _ in range(33)]
for i in range(1, 21):
    board[i] = i * 2
board[21] = 0
board[22], board[23], board[24] = 13, 16, 19
board[25], board[26] = 22, 24
board[27], board[28], board[29] = 28, 27, 26
board[30], board[31], board[32] = 25, 30, 35
dul = [0 for _ in range(33)]
def dfs(depth, score):
    global score_max
    if depth == 10:
        score_max = max(score_max, score)
        return

    for i in range(4):
        # 말 현재 위치에서 주사위 만큼 이동
        x, now_x, num = horse[i], horse[i], dice[depth]
        if x in [5, 10, 15]:
            if x == 5:
                x = 22
            elif x == 10:
                x = 25
            else:
                x = 27
            num -= 1
        if x + num <= 21:
            x += num
        else:
            for _ in range(num):
                x = connet[x]
        if dul[x] and x != 21:
            continue
        dul[now_x], dul[x], horse[i] = 0, 1, x
        dfs(depth+1, score+board[x])
        dul[now_x], dul[x], horse[i] = 1, 0, now_x
score_max = 0
dfs(0, 0)
print(score_max)

 

💻 소스코드 (JAVA)

// BOJ - 주사위 윷놀이(17825번)
// DFS + 구현

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

public class Main_17825 {
	public static int[] dice;
	public static int ans;
	
	public static int[] connect;
	public static int[] score;
	public static boolean[] check;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		dice = new int[10];
		String[] data = br.readLine().split(" ");
		for(int i=0;i<10;i++) {
			dice[i] = Integer.parseInt(data[i]);
		}
		
		connect = new int[33];
		score = new int[33];
		
		for(int i=0;i<21;i++) {
			connect[i] = i+1;
			score[i] = i*2;
		}
		// 도착
		connect[21] = 21;
		score[21] = 0;
		
		// 10 안  (22 ~ 24)
		connect[22] = 23;
		connect[23] = 24;
		connect[24] = 30;
		score[22] = 13;
		score[23] = 16;
		score[24] = 19;
		
		// 20 안 (25 ~ 26)
		connect[25] = 26;
		connect[26] = 30;
		score[25] = 22;
		score[26] = 24;
		
		// 30 안 (27 ~ 32)
		connect[27] = 28;
		connect[28] = 29;
		connect[29] = 30;
		connect[30] = 31;
		connect[31] = 32;
		connect[32] = 20;
		
		score[27] = 28;
		score[28] = 27;
		score[29] = 26;
		score[30] = 25;
		score[31] = 30;
		score[32] = 35;
		
		ans = 0;
		check = new boolean[33];
		dfs(new int[5], 0, 0);
		System.out.println(ans);
	}
	
	public static void dfs(int[] horse, int depth, int sum) {
		if(depth == 10) {

			ans = Math.max(ans, sum);
			return;
		}
		
		for(int i=0;i<5;i++) {
			int x = horse[i];
			int now = horse[i];
			int move = dice[depth];

			if(x == 5) {
				x = 22;
				move--;
			} else if(x==10) {
				x = 25;
				move--;
			} else if(x==15) {
				x = 27;
				move--;
			}

			if(x+move <= 21) {
				x += move;
			} else {
				for(int m=0;m<move;m++) {
					x = connect[x];
				}
			}
	
			
			if(check[x] &&  x != 21) {
				continue;
			}

			check[x] = true;
			check[now] = false;
			horse[i] = x;
		
			dfs(horse, depth+1, sum+score[x]);
			
			check[x] = false;
			check[now] = true;
			horse[i] = now;
			

		}
	}
	

}