#14890. 경사로
Problem
- N x N 지도, 각 칸의 높이가 적힘
- 길은 한 행 또는 한 열 → 길에 속한 모든 칸의 높이가 모두 같아야 지나갈 수 있음
- 또는 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있음( 경사로 높이 1, 길이 L), 경사로 개수는 매우 많음
경사로 놓을 수 있는 경우
- 낮은 칸과 높은 칸의 차이가 1인 경우
- L개의 칸이 같은 높이로 연속되게 있어야 한다.
Solution
한 행
- 맨 왼쪽에서부터 오른쪽으로 탐색한다. (첫 번째 원소부터 마지막 원소 바로 이전까지)
- 현재 탐색한 원소와 바로 다음 원소와의 차이를 구한다.
- +1인 경우
다음 원소부터 경사로 길이만큼 오른쪽으로 탐색을 시작한다.
탐색하면서 다음 경우를 확인한다.
범위를 벗어날 경우(n이상) or 경사로 길이만큼 같은 높이가 아닐 때 종료
그게 아니면 경사로를 놓는다. - -1인 경우
현재 원소부터 경사로 길이만큼 왼쪽으로 탐색을 시작한다.
탐색하면서 다음 경우를 확인한다.
범위를 벗어날 경우(0미만) or 경사로 길이만큼 같은 높이가 아닐 때 or 경사로가 놓여있을 때 종료
그게 아니면 경사로를 놓는다. - 차이가 1 초과 -1 미만인 경우 종료
- 그게 아니라면 성공
왼쪽에서 오른쪽으로 탐색하기에
한 열 또한 위와 마찬가지로 구현한다.
1 Try
- 하…
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
using namespace std;
int n, len, ans;
int map[101][101];
bool check[101][101];
bool checkRow(int row) {
for (int j = 0; j < n - 1; ++j) {
if (map[row][j] - map[row][j + 1] == 1) {
for (int start = j + 1; start <= j + len; ++start) {
if (start >= n) return false; // 범위를 벗어나는 경우
if (map[row][j + 1] != map[row][start]) return false; // 칸의 높이가 같지 않을 때
check[row][start] = true; // 경사로 놓기
}
}
else if (map[row][j] - map[row][j + 1] == -1) {
for (int start = j; start > j - len; --start) {
if (start < 0) return false; // 범위를 벗어나는 경우
if (map[row][j] != map[row][start]) return false;
if (check[row][start]) return false;
check[row][start] = true;
}
}
else if (map[row][j] - map[row][j + 1] > 1 || map[row][j] - map[row][j + 1] < -1)
return false;
}
return true;
}
bool checkCol(int col) {
for (int i = 0; i < n - 1; ++i) {
if (map[i][col] - map[i + 1][col] == 1) {
for (int start = i + 1; start <= i + len; ++start) {
if (start >= n) return false;
if (map[i + 1][col] != map[start][col]) return false;
check[start][col] = true;
}
}
else if (map[i][col] - map[i + 1][col] == -1) {
for (int start = i; start > i - len; --start) {
if (start < 0) return false;
if (map[i][col] != map[start][col]) return false;
if (check[start][col]) return false;
check[start][col] = true;
}
}
else if (map[i][col] - map[i + 1][col] > 1 || map[i][col] - map[i + 1][col] < -1)
return false;
}
}
int main() {
scanf("%d %d", &n, &len);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &map[i][j]);
}
}
for (int row = 0; row < n; ++row) {
if(checkRow(row)) ans++;
}
memset(check, 0, sizeof(check));
for (int col = 0; col < n; ++col) {
if (checkCol(col)) ans++;
}
printf("%d\n", ans);
return 0;
}checkCol함수에 return true 즉 반환값을 넣어주지 않았기에 틀렸다고 나왔다. bool 함수는 반드시 true와 false 둘 다 반환해주자.
이걸 몰라서 계속 문제만 주구장창 봤음…ㅠ
2 Try
1 |
|