쵼쥬
쵼쥬의 개발공부 TIL
쵼쥬
전체 방문자
오늘
어제
  • 분류 전체보기 (276)
    • 코딩테스트 (192)
      • [알고리즘] 알고리즘 정리 (7)
      • [백준] 코딩테스트 연습 (126)
      • [프로그래머스] 코딩테스트 연습 (59)
    • Spring (71)
      • [인프런] 스프링 핵심 원리- 기본편 (9)
      • [인프런] 스프링 MVC 1 (6)
      • [인프런] 스프링 MVC 2 (4)
      • [인프런] 실전! 스프링 부트와 JPA 활용1 (7)
      • [인프런] 실전! 스프링 부트와 JPA 활용2 (5)
      • [인프런] 실전! 스프링 데이터 JPA (7)
      • [인프런] 실전! Querydsl (7)
      • JWT (5)
      • [인프런] Spring Cloud (17)
      • [인프런] Spring Batch (4)
    • Java (6)
      • [Java8] 모던인자바액션 (4)
      • [부스트코스] 웹 백엔드 (2)
      • [패스트캠퍼스] JAVA STREAM (0)
    • CS (6)
      • 디자인 패턴과 프로그래밍 패터다임 (2)
      • 네트워크 (4)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • jpa
  • 자바
  • 인프런
  • 위클리 챌린지
  • 프로그래머스
  • 구현
  • Spring Data JPA
  • 백준
  • 스프링
  • 알고리즘
  • MVC
  • BFS
  • spring
  • 비트마스킹
  • 백분
  • querydsl
  • 코딩테스트
  • 부스트코스
  • 누적합
  • 타임리프

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
쵼쥬

쵼쥬의 개발공부 TIL

주사위 윷놀이 - 17825번
코딩테스트/[백준] 코딩테스트 연습

주사위 윷놀이 - 17825번

2022. 5. 5. 20:20


package com.company;

import java.io.*;
import java.util.*;

public class Main {

    static int[][] blue = {{10, 13, 16, 19, 25, 30, 35, 40}, {20, 22, 24, 25, 30, 35, 40}, {30, 28, 27, 26, 25, 30, 35, 40}};
    static boolean[] check, checkBlue;
    static int[][] horse;
    static int[] move = new int[10];

    static int answer = 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++) {
            move[i] = Integer.parseInt(st.nextToken());
        }
        horse = new int[4][3];
        check = new boolean[41];
        checkBlue = new boolean[41];
        dfs(0, 0);
        System.out.println(answer);
    }

    static void dfs(int index, int score) {
        answer = Math.max(score, answer);

        if (index >= 10) {
            return;
        }

        for (int i = 0; i < horse.length; i++) {
            if (horse[i][0] == -1) {
                continue;
            }

            if (horse[i][1] == 0) {
                int next = move[index] * 2 + horse[i][0];

                if (next <= 40) {

                    if (check[next]) {
                        continue;
                    }
                    int temp = horse[i][0];
                    boolean ch = false;
                    check[horse[i][0]] = false;
                    horse[i][0] = next;
                    check[horse[i][0]] = true;

                    if (horse[i][0] % 10 == 0 && horse[i][0] < 40) {
                        horse[i][1] = horse[i][0] / 10;
                        ch = true;
                    }

                    dfs(index + 1, score + horse[i][0]);
                    check[horse[i][0]] = false;
                    horse[i][0] = temp;
                    check[horse[i][0]] = true;
                    if (ch) {
                        horse[i][1] = 0;
                    }
                } else {
                    int temp = horse[i][0];
                    check[horse[i][0]] = false;
                    horse[i][0] = -1;
                    dfs(index + 1, score);
                    horse[i][0] = temp;
                    check[horse[i][0]] = true;
                }
            } else {
                if (horse[i][2] + move[index] < blue[horse[i][1] - 1].length) {
                    int nextIndex = horse[i][2] + move[index];
                    int next = blue[horse[i][1] - 1][nextIndex];
                    if (checkBlue[next] || (next == 40 && check[40])) {
                        continue;
                    }
                    if (next == 40) {
                        check[next] = true;
                    }
                    boolean ch = false;
                    int temp = horse[i][0];
                    if (horse[i][0] % 10 == 0 && horse[i][2] == 0) {
                        check[horse[i][0]] = false;
                        ch = true;
                    }
                    checkBlue[next] = true;
                    horse[i][0] = next;
                    horse[i][2] += move[index];
                    checkBlue[temp] = false;

                    dfs(index + 1, score + horse[i][0]);

                    if (next == 40) {
                        check[next] = false;
                    }
                    checkBlue[next] = false;
                    horse[i][0] = temp;
                    horse[i][2] -= move[index];
                    if (ch) {
                        check[horse[i][0]] = true;
                    }
                    if (horse[i][2] != 0) {
                        checkBlue[horse[i][0]] = true;
                    }
                } else {
                    int temp = horse[i][0];
                    checkBlue[temp] = false;
                    horse[i][0] = -1;
                    if (temp == 40) {
                        check[40] = false;
                    }
                    dfs(index + 1, score);
                    checkBlue[temp] = true;
                    horse[i][0] = temp;
                    if (temp == 40) {
                        check[40] = true;
                    }
                }
            }
        }
    }
}

'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글

컨베이어 벨트 위의 로봇 - 20055번  (0) 2022.05.13
도노미노도미노 2 - 20061번  (0) 2022.05.09
원판돌리기 - 17822번  (0) 2022.05.03
새로운 게임 2  (0) 2022.05.03
게리맨더링 2 - 17779번  (0) 2022.04.27
    '코딩테스트/[백준] 코딩테스트 연습' 카테고리의 다른 글
    • 컨베이어 벨트 위의 로봇 - 20055번
    • 도노미노도미노 2 - 20061번
    • 원판돌리기 - 17822번
    • 새로운 게임 2
    쵼쥬
    쵼쥬

    티스토리툴바