백준 17825번 주사위 윷놀이 Java/자바 - 2019 삼성 SW 역량테스트 기출문제
문제
1~5가 적혀진 주사위를 던져서 윷판에 말 4개를 이동시키면서 점수의 최대값을 구하는 문제이다.
도착을 하면 말은 더이상 움직일 수 없고 이동하려는 칸에 다른 말이 있으면 그 말은 이동이 불가능하다. 파란색이 칠해진 점수판에 올라간경우 이동방향이 파란색 화살표 방향으로 진행해야 한다.(기존은 빨간색 화살표 방향)
접근
- 윷판의 특수하므로 강 경로에 따른 이동을 체크하기 위해 특수한 배열이 필요
- 이동하는 말 4개의 모든 경우의 수를 구한다 DFS (각 말이 어떻게 움직이느냐에 따라 점수가 달라지므로 모든 경우의 수 필요)
- 정해진 말의 이동 순서에 따라 주사위가 나온만큼 이동
- 이동 불가능 체크(현재의 위치 마지막인가? 이동하려는 칸에 누군가 있는가?)
- 이동이 가능하다면 윷판의 점수가 10,20,30 일때 점프하도록 설정, 현재위치 + 이동거리가 도착지점을 초과하는 경우 도착으로 간주
풀이
1번
public class DiceYook_17825 {
static int answer = 0;
static int [] a = {
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0, //0 ~ 21
10, 13, 16, 19, 25, 30, 35, 40, 0, //22 ~ 30
20, 22, 24, 25, 30, 35, 40, 0, //31 ~ 38
30, 28, 27, 26, 25, 30, 35, 40, 0}; //39 ~ 47
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int [] player = new int[10]; //주사위 10번 던질동안 말 1,2,3,4 번중 누가 움직일 것인지
int [] dice = new int[10];
for(int i=0 ; i<10 ; i++)
dice[i] = sc.nextInt();
dfs(10, 0, player, dice);
System.out.println(answer);
sc.close();
}
public static void dfs(int n, int cnt, int [] player, int [] dice) {
if(cnt == 10) {
move(player, dice);
return;
}
for(int i=0 ; i<4 ; i++) {
player[cnt] = i;
dfs(n, cnt+1, player, dice);
}
}
public static void move(int [] player, int [] dice) {
int a0 = 0; int a1 = 0; int a2 = 0; int a3 = 0;
int score = 0;
for(int i=0 ; i<10 ; i++) {
int d = dice[i];
int p = player[i]; //p : 0~4
switch(p) {
case 0:
if(isEnd(a0)) return;
else {
if(isDuplicated(a0, a1, a2, a3, d)) return;
int temp = jumpCheck(a0, d);
a0 = temp;
score += a[a0];
}
break;
case 1:
if(isEnd(a1)) return;
else {
if(isDuplicated(a1, a0, a2, a3, d)) return;
int temp = jumpCheck(a1, d);
a1 = temp;
score += a[a1];
}
break;
case 2:
if(isEnd(a2)) return;
else {
if(isDuplicated(a2, a0, a1, a3, d)) return;
int temp = jumpCheck(a2, d);
a2 = temp;
score += a[a2];
}
break;
case 3:
if(isEnd(a3)) return;
else {
if(isDuplicated(a3, a0, a1, a2, d)) return;
int temp = jumpCheck(a3, d);
a3 = temp;
score += a[a3];
}
break;
}
}
answer = Math.max(answer, score);
}
//아래 생략
}
- 10, 20, 30의 윳판에 따른 경로를 위해 특수한 배열 생성
- 그리고 이동을 체크하기 위한
- dfs를 통해 어느 순서로 말을 이동시킬지 모든 경우의 수 구하기
- 이동 불가능한 상태 확인하기 isEnd() - 현재의 위치가 마지막위치인지, isDuplicated() - 이동하려는 칸에 다른 말이 있는지
- 이동이 가능하다면 jumpCheck()를 통해 새로운 위치 가져오기
public class DiceYook_17825 {
//중간 생략
public static int jumpCheck(int v, int d) {
int temp = v + d;
if(v < 21) {
if(temp >= 21) temp = 21;
} else if(v < 30) {
if(temp >= 30) temp = 30;
} else if(v < 38) {
if(temp >= 38) temp = 38;
} else if(v < 47) {
if(temp >= 47) temp = 47;
}
if(temp == 5) return 22;
if(temp == 10) return 31;
if(temp == 15) return 39;
return temp;
}
public static boolean isEnd(int idx) {
return (idx==21) || (idx==30) || (idx==38) || (idx==47);
}
public static boolean isDuplicated(int p, int p1, int p2, int p3, int d) {
//도착점을 초과하는 위치
if(p < 21 && p+d >= 21) return false;
else if(p < 30 && p+d >= 30) return false;
else if(p < 38 && p+d >= 38) return false;
else if(p < 47 && p+d >= 47) return false;
//5, 10, 15 번째는 점프가 발생하는 위치 파란색
int temp = p + d;
if(temp == 5) temp = 22;
if(temp == 10) temp = 31;
if(temp == 15) temp = 39;
//같은 선상에 있는지 체크
if(temp == p1 || temp == p2 || temp == p3) return true;
//25, 30, 35, 40 은 중복 공유위치
if(a[temp] == 25) {
if(a[p1] == 25 || a[p2] == 25 || a[p3] == 25) return true;
} else if(a[temp] == 35) {
if(a[p1] == 35 || a[p2] == 35 || a[p3] == 35) return true;
} else if(a[temp] == 40) {
if(a[p1] == 40 || a[p2] == 40 || a[p3] == 40) return true;
} else if(a[temp] == 30) {
if(temp == 39) {
if(p1 == 39 || p2 == 39 || p3 == 39) return true;
} else if(temp == 27){
if(p1 == 27 || p2 == 27 || p3 == 27) return true;
if(p1 == 35 || p2 == 35 || p3 == 35) return true;
if(p1 == 44 || p2 == 44 || p3 == 44) return true;
} else if(temp == 35) {
if(p1 == 27 || p2 == 27 || p3 == 27) return true;
if(p1 == 35 || p2 == 35 || p3 == 35) return true;
if(p1 == 44 || p2 == 44 || p3 == 44) return true;
} else if(temp == 44) {
if(p1 == 27 || p2 == 27 || p3 == 27) return true;
if(p1 == 35 || p2 == 35 || p3 == 35) return true;
if(p1 == 44 || p2 == 44 || p3 == 44) return true;
}
}
return false;
}
}
jumpCheck()
- 범위를 초과했을 때는 도착지점으로 이동시
- 이동하는 칸의 배열의 값이 10, 20, 30일 경우 점프시킨다.
duplicated()
- 현재의위치 p에서 d만큼 이동한 것이 4개의 윷경로인 (0~21) , (22~30), (31~38), (39~47)을 벗어나지 않는 경우만 확인하면 된다. 그 이외의 경우는 jumpCheck()를 통해 모두 도착지점으로 변경시키기에 고려할 필요없다.
- 이동한 값의 위치인 temp가 다른 말과 겹치는 지 확인
- 겹치지 않을 때 25, 30, 35, 40일 때 추가적인 확인이 필요 (모든 경로에 겹치는 위치이므로)
- 25,35,45의 경우는 값이 중복되면 같은 위치이므로 불가능
- 30의 경우 윷경로의 인덱스를 비교하여 가능여부 판단. 30이 나오는 경우는 27, 35, 44 그리고 39가 있다. 이중에 39번째 인덱스만 윷판에서 다른 위치에 있다.
이 문제는 dfs + simulation의 조합이다. 삼성 코딩 테스트의 문제가 dfs/bfs + 시뮬의 형태로 바뀐것 같다. 이 문제에서의 가장 핵심은 20, 25, 30, 45 에 대한 예외처리가 핵심이다. 확실하게 값을 구분하고자 코드를 줄이지 않았다.
결론
- 삼성전자 들어가고 싶……..