문제
https://www.acmicpc.net/problem/19236
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
접근방법
1) 접근 사고
런타임 에러 때문에 거의 3일을 고민하면서 푼 문제라서 죽을 때까지 잊지 못할 문제인 거 같습니다. 알고리즘의 단계는 밑에 단계로 이루어져 있습니다.
1. 입력값을 받는다.
2. 물고기를 이동시켜준다. 이때 죽은 물고기의 방향은 -1로 표시한다.(모든 물고기를 각 단계마다 움직여야 하는데 -1 물고기는 죽은 물고기 이므로 움직이지 않는다.)
3. 상어의 위치, 방향, 현재 상어가 먹은 점수 합계가 담긴 DFS를 통해서 상어가 움직일 수 있는 모든 경우를 탐색한다.
문제 자체는 물고기의 인덱스가 담긴 4*4 boarad 물고기의 정보를 담고 있는 배열들의 값을 조절해주면 되는 문제였습니다.
문제에서 물고기와 상어의 위치와 방향을 저장해야 하므로 편의를 위해 구조체 변수를 선언한뒤 벡터를 사용했는데 런타임에러(Invalid Pointer) 오류가 나와서 채점이 불가능했습니다. IDE를 Clion을 사용하고 있는데 IDE내에서의 테스트 값과 실행은 정상적으로 이루어지나 내부 어디에서 오류가 나오는 거 같습니다. 코드에서 vector 선언 부분을 배열로 변경해주니 통과는 되었으나 왜 vector를 사용했을 경우 런타임 에러가 나오는지는 이유를 찾지 못했습니다. 생성자 초기화를 통한 쓰레기 값이 생기는 경우가 가장 유력한 문제의 원인이라 생각하였으나 문제의 원인은 아니었습니다. 밑에 런타임 에러가 나오는 코드를 첨부하였는데 혹시 원인을 아시는 분이 있다면 댓글로 알려주시면 감사할 거 같습니다.
2) 시간 복잡도
O(n^2)
3) 배운 점
구조체를 통한 자료형을 만들어서 사용할 때는 배열을 사용하자 (vector 에서 사용하여 나오는 오류의 원인을 찾지 못했으니까..)
4) PS
시간의 효율성을 따지자면 페라리나 람보르기니 같은 슈퍼카의 연비 같지만 저의 끈기를 테스트해볼 수 있던 좋은 계기였습니다. 개발을 할 때 오류를 해결하는 것은 스택오버플로우나 구글링을 하면 거의 해결되었는데 이 문제는 정말 저 스스로 해결할 수밖에 없는 문제이다 보니 2.5일 동안 밥 먹는 시간 제외하고 C++ 문법이랑 내부 라이브러리를 뜯어볼 수 있던 좋은 기회였습니다. 물론 머리를 뜯어가면서 빠진 머리카락들은 아깝네요
정답 코드(통과)
|
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
|
#include <bits/stdc++.h>
using namespace std;
const int MAX = 4;
int board[MAX][MAX];
struct fish {
int y, x, dir;
};
int mx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int my[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
fish fishes[17];
int ret = 0;
int main() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int num, dir;
cin >> num >> dir;
dir--;
fishes[num] = {i, j, dir};
board[i][j] = num;
}
}
int idx = board[0][0];
int sd = fishes[idx].dir;
fishes[idx].dir = -1;
board[0][0] = 0;
auto DFS = [&](int sy, int sx, int sd, int sum, auto &&DFS) -> void {
fish tmpfishes[17];
int tmpboard[MAX][MAX];
memcpy(tmpboard, board, sizeof board);
memcpy(tmpfishes, fishes, sizeof tmpfishes);
auto moveFish = [&]() {
for (int i = 1; i <= 16; i++) {
auto[y, x, d] = fishes[i];
if (d == -1) {
continue;
}
int nd = d;
int nextY, nextX;
for (int dCnt = 0; dCnt < 8; dCnt++) {
nextY = y + my[nd];
nextX = x + mx[nd];
if (nextY >= 0 && nextY < 4 && nextX >= 0 && nextX < 4) {
int idx = board[nextY][nextX];
if (idx == 0) {
nd = (nd == 7) ? 0 : nd + 1;
continue;
}
board[nextY][nextX] = i;
fishes[i] = {nextY, nextX, nd};
board[y][x] = idx;
fishes[idx].y = y;
fishes[idx].x = x;
break;
}
nd = (nd == 7) ? 0 : nd + 1;
}
}
};
moveFish();
for (int i = 1; i <= 3; i++) {
int ny = sy + my[sd] * i;
int nx = sx + mx[sd] * i;
if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {
int idx = board[ny][nx];
if (idx == -1)
continue;
int nsd = fishes[idx].dir;
fishes[idx].dir = -1;
board[sy][sx] = -1;
board[ny][nx] = 0;
DFS(ny, nx, nsd, sum + idx, DFS);
fishes[idx].dir = nsd;
board[sy][sx] = 0;
board[ny][nx] = idx;
} else
break;
}
ret = max(ret, sum);
memcpy(board, tmpboard, sizeof tmpboard);
memcpy(fishes, tmpfishes, sizeof fishes);
};
DFS(0, 0, sd, idx, DFS);
cout << ret << "\n";
}
|
cs |
런타임 에러 코드
|
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
|
#include <bits/stdc++.h>
using namespace std;
const int MAX = 4;
int board[MAX][MAX];
struct fish {
int y, x, dir;
fish() : fish(0,0,0) {}
fish(int y , int x, int dir) : y(y), x(x), dir(dir){}
};
int mx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int my[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
vector<fish> fishes;
int ret = 0;
int main() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int num, dir;
cin >> num >> dir;
dir--;
fishes[num] = {i, j, dir};
board[i][j] = num;
}
}
int idx = board[0][0];
int sd = fishes[idx].dir;
fishes[idx].dir = -1;
board[0][0] = 0;
auto DFS = [&](int sy, int sx, int sd, int sum, auto &&DFS) -> void {
vector<fish> tmpfishes;
int tmpboard[MAX][MAX];
memcpy(tmpboard, board, sizeof board);
//memcpy(tmpfishes, fishes, sizeof tmpfishes);
tmpfishes = fishes;
auto moveFish = [&]() {
for (int i = 1; i <= 16; i++) {
auto[y, x, d] = fishes[i];
if (d == -1) {
continue;
}
int nd = d;
int nextY, nextX;
for (int dCnt = 0; dCnt < 8; dCnt++) {
nextY = y + my[nd];
nextX = x + mx[nd];
if (nextY >= 0 && nextY < 4 && nextX >= 0 && nextX < 4) {
int idx = board[nextY][nextX];
if (idx == 0) {
nd = (nd == 7) ? 0 : nd + 1;
continue;
}
board[nextY][nextX] = i;
fishes[i] = {nextY, nextX, nd};
board[y][x] = idx;
fishes[idx].y = y;
fishes[idx].x = x;
break;
}
nd = (nd == 7) ? 0 : nd + 1;
}
}
};
moveFish();
// for (int i = 0; i < 4; i++) {
// for (int j = 0; j < 4; j++) {
// cout << board[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "===========" << "\n";
for (int i = 1; i <= 3; i++) {
int ny = sy + my[sd] * i;
int nx = sx + mx[sd] * i;
// cout << ny <<" " << nx <<" " << sd <<"\n";
if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {
int idx = board[ny][nx];
if (idx == -1)
continue;
int nsd = fishes[idx].dir;
fishes[idx].dir = -1;
board[sy][sx] = -1;
board[ny][nx] = 0;
DFS(ny, nx, nsd, sum + idx, DFS);
fishes[idx].dir = nsd;
board[sy][sx] = 0;
board[ny][nx] = idx;
} else
break;
}
ret = max(ret, sum);
memcpy(board, tmpboard, sizeof tmpboard);
fishes = tmpfishes;
};
DFS(0, 0, sd, idx, DFS);
cout << ret << "\n";
}
|
cs |
'백준문제풀이 > 구현' 카테고리의 다른 글
| 19238번-스타트택시 (0) | 2021.09.25 |
|---|---|
| 19237번-어른 상어 (0) | 2021.09.24 |
| 17779번-게리멘더링2 (0) | 2021.09.16 |
| 17142번-연구소3 (0) | 2021.09.15 |
| 17140번-이차원 배열과 연산 (0) | 2021.09.15 |