2021 하반기 삼성 기출이 올라왔다해서 후다닥 풀어봤다
이 문제는 총 55분 가량 걸렸는데 문제를 잘못 읽어서 한 20분 넘게 날려서 아쉬웠다
삼성 기출을 쉽게 푸는 법을 설명하기 위해 어떤식으로 접근하였는지 서술해보고자 한다
먼저 주사위 모양을 살펴보았다
나는 주석처리된 부분처럼 배열의 인덱스를 정하였다
그 후 주사위가 구를 때 어떤 위치에 어떤 인덱스가 가게 되는지를 살펴보았다
다행히 문제에서 힌트를 주었다
먼저 문제에서 준 주사위 초기값
주사위 배열을 초기값인 2,4,1,3,5,6으로 채워주었다
그다음 초기값이 동쪽으로 변할 때 어떻게 변화하는지 살펴보았다
살펴보면 1,5번 인덱스는 그대로 2번은 3번으로, 3번은 4번으로, 4번은 6번으로, 6번은 2번으로 바뀐 것을 알 수 있다
이런 규칙에 따라서 move dice 함수를 만들어주었다
노가다가 들어가긴 하지만 주사위 문제를 몇 문제 풀어본 결과 나는 이게 가장 빠른 풀이라고 생각한다
동쪽을 알았다면 서쪽은 매우 쉽다
바뀌는 부분만 반대로 만들면 된다
다음에는 북,남쪽이 필요하다
이 주사위가 남쪽으로 이동하면 이렇게 된다고 문제에서 알려주었다
실제 시험장에서도 알려주었는지는 모르겠지만 이렇게 친절한 문제라니ㅋㅋㅋ
안알려줬으면 머리속에서 주사위 돌리느라 고생깨나 했을 듯 하다
아무튼 이 그림을 보면 남쪽으로 바뀔때는 2,4가 그대로 1은 3으로, 3은 5로, 5는 6으로, 6은 1로 간다
이러한 규칙에 따라 move dice 함수를 먼저 만들어주었다
그 다음은 주사위 이동을 실제로 시켜보았다
next 위치를 한 번 만들어 보고 그 위치가 범위를 벗어난다면 방향에 2를 더해 (반대방향) 다시 이동시켜주었다
그 과정에서 k의 증가가 일어나면 안되니까 한 번 감소시켜주었다
그 다음은 해당 위치에서 얻을 수 있는 점수를 계산해야한다
나는 여기서 실수 했다
실제로 주사위가 A,B에 따른 방향을 포함하여 이동하는 거리를 계산하는 줄 알았는데 주사위의 이동과 별개로 그냥 갈 수 있는 거리였다
쉬운 문제를 너무 어렵게 생각했던 것 같다
print dice는 이 때 만든 함수인데 주사위를 잘못 이동시켰나..?싶어서 만들었다
후에 여러 테스트케이스를 검증할때도 사용하였으니 하나 만들어두면 좋을 듯 하다
아무튼 해당 위치에서 dfs를 이용해 이동할 수 있는 위치의 개수를 세어 주었고 그 개수를 B와 곱하여 점수를 계산했다
이러한 이동을 K번 반복하면 문제 끝!
주사위의 이동 구현 + dfs,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
123
124
125
126
127
128
129
|
#include <stdio.h>
int dice[7] = {0,2,4,1,3,5,6};
int dice_tmp[7];
int grid[21][21];
int visit[21][21];
// 1
// 2 3 4
// 5
// 6
int dc[4] = {0,1,0,-1};
int dr[4] = {-1,0,1,0};
int N,M,K;
void print_dice(){
printf(" %d \n",dice[1]);
printf("%d %d %d\n",dice[2],dice[3],dice[4]);
printf(" %d \n",dice[5]);
printf(" %d \n",dice[6]);
printf("\n");
}
void move_dice(int dir){
if(dir==0){ // 북
dice_tmp[6] = dice[1];
dice_tmp[2] = dice[2];
dice_tmp[1] = dice[3];
dice_tmp[4] = dice[4];
dice_tmp[3] = dice[5];
dice_tmp[5] = dice[6];
}
else if(dir==1){ // 동
dice_tmp[1] = dice[1];
dice_tmp[3] = dice[2];
dice_tmp[4] = dice[3];
dice_tmp[6] = dice[4];
dice_tmp[5] = dice[5];
dice_tmp[2] = dice[6];
}
else if(dir==2){ // 남
dice_tmp[3] = dice[1];
dice_tmp[2] = dice[2];
dice_tmp[5] = dice[3];
dice_tmp[4] = dice[4];
dice_tmp[6] = dice[5];
dice_tmp[1] = dice[6];
}
else{ // 서
dice_tmp[1] = dice[1];
dice_tmp[6] = dice[2];
dice_tmp[2] = dice[3];
dice_tmp[3] = dice[4];
dice_tmp[5] = dice[5];
dice_tmp[4] = dice[6];
}
for(int i = 1 ; i <= 6 ; i++)
dice[i] = dice_tmp[i];
}
void visit_init(){
for(int i = 1 ; i <= 20 ; i++){
for(int j = 1; j <= 20 ; j++)
visit[i][j] = 0;
}
}
void count_move(int r, int c, int B, int dist){
if(visit[r][c]) return;
visit[r][c] = 1;
for(int i = 0 ; i < 4 ; i++){
int next_r = r + dr[i];
int next_c = c + dc[i];
if(next_r<=0 || next_c<=0 || next_r > N || next_c > M) continue;
if(grid[next_r][next_c]==B) count_move(next_r,next_c,B,dist+1);
}
}
int count_visit(){
int res = 0;
for(int i = 1 ; i <= 20 ; i++){
for(int j = 1; j <= 20 ; j++)
if(visit[i][j]) res++;
}
return res;
}
int main(){
scanf("%d %d %d",&N,&M,&K);
for(int i = 1 ; i <= N ; i++){
for(int j = 1 ; j <= M ; j++)
scanf("%d",&grid[i][j]);
}
int r = 1, c = 1, dir = 1, score = 0,b,k=1;
bool isFirst = true;
for(int k = 1 ; k <= K ; k++){
int next_r = r+dr[dir];
int next_c = c+dc[dir];
// 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
if(next_r<=0 || next_c<=0 || next_r > N || next_c > M){
dir = (dir+2)%4; // 반대방향
k--;
continue;
}
// 주사위 배열 바꾸기
move_dice(dir);
//print_dice();
// 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
int A = dice[6];
int B = grid[next_r][next_c];
if(A>B) dir = (dir+1)%4;
else if(A<B) dir = (dir+3)%4;
visit_init();
count_move(next_r,next_c,B,0);
int C = count_visit();
score += B*C;
r = next_r; c = next_c;
}
printf("%d\n",score);
}
|
cs |
'알고리즘' 카테고리의 다른 글
[Rust] 백준 10807번 개수 세기 (1) | 2023.01.20 |
---|---|
[C++] 별자리 만들기 (0) | 2021.10.29 |
[C++] 가장 가까운 두 점 (0) | 2021.10.16 |
[SWEA] 균형점 (0) | 2021.09.04 |
[SWEA] 소수 완제품 확률 (0) | 2021.08.31 |