99클럽 코테 스터디 35일차 TIL (미들러): [백준][Java] 주사위 윷놀이 - 골드2

 

문제 보기

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

 

 

풀이

좀 무식한 방법을 사용해서 윷놀이 판을 만들었다.

칸에 인덱스를 부여하고

 

{ { 0, 1, -1 }, 
{ 2, 2, -1 }, 
{ 4, 3, -1 }, 
{ 6, 4, -1 }, 
{ 8, 5, -1 }, 
{ 10, 6, 22 }, 
{ 12, 7, -1 }, 
{ 14, 8, -1 }, 
{ 16, 9, -1 }, 
{ 18, 10, -1 }, 
{ 20, 11, 29 }, 
{ 22, 12, -1 }, 
{ 24, 13, -1 }, 
{ 26, 14, -1 }, 
{ 28, 15, -1 }, 
{ 30, 16, 26 }, 
{ 32, 17, -1 }, 
{ 34, 18, -1 }, 
{ 36, 19, -1 }, 
{ 38, 20, -1 }, 
{ 40, 21, -1 }, 
{ 0, 21, -1 }, 
{ 13, 23, -1 }, 
{ 16, 24, -1 }, 
{ 19, 25, -1 }, 
{ 25, 31, -1 }, 
{ 28, 27, -1 }, 
{ 27, 28, -1 }, 
{ 26, 25, -1 }, 
{ 22, 30, -1 }, 
{ 24, 25, -1 }, 
{ 30, 32, -1 }, 
{ 35, 20, -1 } }

2차원 배열을 만들어 현재 칸의 점수, 다음 칸, 파란 칸일 경우 세 번째에 파란 다음 칸을 넣었다.

빨간 칸일 경우 여기에 -1이 들어간다.

도착 지점의 다음 칸은 도착 지점으로 해두었다.

 

  private static void dfs(int sum, int[] index, boolean[] isHave, int depth) {
    if(depth == 10) {
      max = Math.max(max, sum);
      return;
    }

    for(int i = 0; i < 4; i++) {
      if(index[i] == 21) continue;

      int temp = index[i];
      int cur = temp;
      int count = arr[depth];

      if(map[cur][2] != -1) {
        cur = map[cur][2];
        count--;
      }

      while (count-- > 0) {
        cur = map[cur][1];
      }

      if(isHave[cur] && cur != 21) continue;

      isHave[temp] = false;
      isHave[cur] = true;
      index[i] = cur;

      dfs(sum + map[index[i]][0], index, isHave, depth + 1);

      isHave[temp] = true;
      isHave[cur] = false;
      index[i] = temp;
    }
  }

그리고 백트래킹을 사용하였다.

4개의 말이 있으니 이번에 어떤 말을 움직일지 모든 경우의 수를 살펴보았다.

 

if(index[i] == 21) continue;

우선 21번 노드는 도착점이기 때문에 현재 말이 도착점에 있을 경우 건너뛴다.

 

  int temp = index[i];
  int cur = temp;
  int count = arr[depth];

  if(map[cur][2] != -1) {
    cur = map[cur][2];
    count--;
  }

그리고 temp에 현재 말의 위치를 저장.

cur을 이용해 도착 장소를 계산할 것이다.

주사위의 눈금은 count에 저장.

 

만역 현재 칸의 2번 인덱스가 -1이 아닐 경우 파란 칸이란 뜻이기 때문에 그쪽으로 이동하고 이동 횟수를 차감한다.

 

  while (count-- > 0) {
    cur = map[cur][1];
  }

이동 횟수가 전부 차감될 때까지 다음 칸으로 이동한다.

 

if(isHave[cur] && cur != 21) continue;

isHave는 특정 칸에 말이 있는지 없는지를 확인하기 위한 배열이다.

도착 칸에 이미 말이 있으며 그게 도착 칸이 아닐 경우 continue

 

  isHave[temp] = false;
  isHave[cur] = true;
  index[i] = cur;

  dfs(sum + map[index[i]][0], index, isHave, depth + 1);

  isHave[temp] = true;
  isHave[cur] = false;
  index[i] = temp;

마지막으로 시작 칸(이전 도착 칸)은 false로 바꾸고

현재 도착 칸을 true로 바꿔주자.

말 위치 배열도 수정해 준다.

 

재귀를 호출한 뒤

isHave, index 배열을 복구한다.

 

 

전체 코드

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

public class Main {
  private static int[] arr = new int[10];
  private static int max = 0;
  private static int[][] map =
      { { 0, 1, -1 },
          { 2, 2, -1 },
          { 4, 3, -1 },
          { 6, 4, -1 },
          { 8, 5, -1 },
          { 10, 6, 22 },
          { 12, 7, -1 },
          { 14, 8, -1 },
          { 16, 9, -1 },
          { 18, 10, -1 },
          { 20, 11, 29 },
          { 22, 12, -1 },
          { 24, 13, -1 },
          { 26, 14, -1 },
          { 28, 15, -1 },
          { 30, 16, 26 },
          { 32, 17, -1 },
          { 34, 18, -1 },
          { 36, 19, -1 },
          { 38, 20, -1 },
          { 40, 21, -1 },
          { 0, 21, -1 },
          { 13, 23, -1 },
          { 16, 24, -1 },
          { 19, 25, -1 },
          { 25, 31, -1 },
          { 28, 27, -1 },
          { 27, 28, -1 },
          { 26, 25, -1 },
          { 22, 30, -1 },
          { 24, 25, -1 },
          { 30, 32, -1 },
          { 35, 20, -1 } };

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());

    for(int i = 0; i < 10; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    dfs(0, new int[4], new boolean[33], 0);
    bw.write(max + "");

    bw.flush();
    bw.close();
  }

  private static void dfs(int sum, int[] index, boolean[] isHave, int depth) {
    if(depth == 10) {
      max = Math.max(max, sum);
      return;
    }

    for(int i = 0; i < 4; i++) {
      if(index[i] == 21) continue;

      int temp = index[i];
      int cur = temp;
      int count = arr[depth];

      if(map[cur][2] != -1) {
        cur = map[cur][2];
        count--;
      }

      while (count-- > 0) {
        cur = map[cur][1];
      }

      if(isHave[cur] && cur != 21) continue;

      isHave[temp] = false;
      isHave[cur] = true;
      index[i] = cur;

      dfs(sum + map[index[i]][0], index, isHave, depth + 1);

      isHave[temp] = true;
      isHave[cur] = false;
      index[i] = temp;
    }
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/17825.%E2%80%85%EC%A3%BC%EC%82%AC%EC%9C%84%E2%80%85%EC%9C%B7%EB%86%80%EC%9D%B4

CodingTest_AutoSave/백준/Gold/17825. 주사위 윷놀이 at main · MetroDefro/CodingTest_AutoSave