코테/삼성 SW 역량
정육면체 한번 더 굴리기 (JAVA)
imname1am
2024. 2. 12. 22:19
반응형
📖 문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
💡 풀이 방식
• 시뮬레이션 + BFS
① 한 칸 전진해 점수 갱신 → ② 주사위 굴리고 방향 조정
1. 현재 방향으로 한 칸 전진하여 좌표 값을 갱신하고, 해당 칸에서 bfs를 통해 현재 칸에서 얻을 수 있는 점수를 구해 합을 갱신한다.
(한 칸 전진 시 격자판을 벗어난 경우, 반대 방향으로 되도록 조정해준다.)
2. 주사위가 놓인 상태를 조정한다. 이를 위해 현재 이동 방향에 맞춰 주사위를 굴리며 보이는 면 배열 dice를 갱신한다. 그리고 나서 주사위 바닥면의 값과 현재 칸의 값을 비교해 회전 방향을 조정한다.
private static void rollDice() {
// 1. 주사위 굴리기
int[] tmp = dice.clone();
if(dir == 0) {
dice = new int[]{7 - tmp[2], tmp[1], tmp[0]};
}
else if(dir == 1) {
dice = new int[]{7 - tmp[1], tmp[0], tmp[2]};
}
else if(dir == 2) {
dice = new int[] {tmp[2], tmp[1], 7 - tmp[0]};
}
else if(dir == 3) {
dice = new int[] {tmp[1], 7 - tmp[0], tmp[2]};
}
// 2. 주사위 바닥면 비교하기
int bottom = 7 - dice[0];
if(bottom > grid[x][y]) { // 시계 90도 회전
dir = (dir + 1) % 4;
}
else if(bottom < grid[x][y]) { // 반시계 90도 회전
dir = (dir - 1 + 4) % 4;
}
}
💥 유의사항
BFS 진행 전 방문 배열은 매번 초기화해줘야 한다!!
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {0,1,0,-1}; // (시계 방향) 오른쪽 아래쪽 왼쪽 위쪽
static int[] dy = {1,0,-1,0};
static int n,m;
static int[][] grid;
static boolean[][] visited;
static int[] dice = new int[] {1,2,3}; // 윗면 앞면 오른쪽면
static int x = 0, y = 0, dir = 0;
static int sum = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
grid = new int[n][n];
visited = new boolean[n][n];
for(int i = 0 ; i < n ; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0 ; j < n ; j++) {
grid[i][j] = Integer.parseInt(st.nextToken());
}
}
while(m --> 0) {
simulate();
}
System.out.println(sum);
}
private static void simulate() {
// 1. 아랫면 확인해 방향 값 설정하기
int nx = x + dx[dir];
int ny = y + dy[dir];
// 격자판 벗어난 경우 조정
if(!inRange(nx, ny)) {
dir = (dir + 2) % 4;
nx = x + dx[dir];
ny = y + dy[dir];
}
x = nx;
y = ny;
sum += bfs(x, y);
// 2. 주사위 놓인 상태 조정하기
rollDice();
}
private static void rollDice() {
// 1. 주사위 굴리기
int[] tmp = dice.clone();
if(dir == 0) {
dice = new int[]{7 - tmp[2], tmp[1], tmp[0]};
}
else if(dir == 1) {
dice = new int[]{7 - tmp[1], tmp[0], tmp[2]};
}
else if(dir == 2) {
dice = new int[] {tmp[2], tmp[1], 7 - tmp[0]};
}
else if(dir == 3) {
dice = new int[] {tmp[1], 7 - tmp[0], tmp[2]};
}
// 2. 주사위 바닥면 비교하기
int bottom = 7 - dice[0];
if(bottom > grid[x][y]) { // 시계 90도 회전
dir = (dir + 1) % 4;
}
else if(bottom < grid[x][y]) { // 반시계 90도 회전
dir = (dir - 1 + 4) % 4;
}
}
private static int bfs(int x, int y) {
for(int i = 0 ; i < n ; i++) { // 매번 초기화해줘야 함!! ⭐
for(int j = 0 ; j < n ; j++)
visited[i][j] = false;
}
visited[x][y] = true;
int target = grid[x][y];
int total = 0;
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {x, y});
while(!q.isEmpty()) {
int[] now = q.poll();
total += target;
for(int d = 0 ; d < 4 ; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if(inRange(nx, ny) && !visited[nx][ny] && grid[nx][ny] == target) {
visited[nx][ny] = true;
q.add(new int[] {nx, ny, total});
}
}
}
return total;
}
private static boolean inRange(int x, int y) {
return (0 <= x && x < n && 0 <= y && y < n);
}
}
|
cs |
💦 어려웠던 점
- 이동시키고 주사위 굴리고 방향 전환하는 이 순서가 머리에서 뒤죽박죽이었다... 제대로 순서를 정리하고 하자...
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |
(참고)
✔ 코드트리
반응형