문제 링크
https://www.acmicpc.net/problem/14890
문제 접근
점 (i, j)와 (i, j + 1)의 비교의 경우의 수는 다음과 같다.
1. 높이의 차가 2 이상인 경우
2. 같은 높이인 경우
3. 차가 1일때, 오르막인 경우
4. 차가 1일때, 내리막인 경우
높이의 차가 2인 경우, 해당 길은 지날 수 없다.
까다로운 부분은 오르막, 내리막의 경우인데, 낮은 지대에 경사로의 크기 L을 수용할 만한 공간이 있음을 체크해야한다.
- (i, j + 1)이 오르막인 경우, (i, j)가 더 낮은 지대이므로 (i, j)부터 뒤로 가면서 낮은 지대의 갯수가 L보다 크거나 같으면 이동 가능
- (i, j + 1)이 내리막인 경우, (i, j + 1)이 더 같은 지대이므로, (i, j + 1)부터 앞으로 가면서 낮은 지대의 갯수가 L보다 크거나 같으면 이동 가능
또 다른 중요한 점은 내리막과 오르막이 연달아 있는 경우에서 경사로를 겹쳐서 놓는 경우는 허가되지 않는다는 것이다. 따라서 visit 배열을 통해 경사로가 놓인 위치를 표시해줘야한다.
소스 코드
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;
int N, L, map[MAX][MAX], visit[MAX];
void input() {
cin >> N >> L;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
cin >> map[i][j];
}
int solve() {
int differ, ret = 0, low_area = 0;
for (int i = 0; i < N; ++i) {
memset(visit, 0, sizeof(visit));
// 가로 검사
for (int j = 1; j < N; ++j) {
differ = map[i][j - 1] - map[i][j];
if (abs(differ) > 1) break; // 차이가 2 이상이면 갈 수 있는 길이 아님
// 오르막인 경우
if (differ < 0) {
low_area = 0;
for (int l = j - 1; l >= 0; --l) { // j가 높은 지대이므로 j-1이전을 카운트
if (visit[l] || map[i][l] != map[i][j - 1]) break;
++low_area;
}
if (low_area >= L) { // 다리놓을 공간이 충분하므로 L개만큼 방문 표시하자
low_area = L;
for (int l = j - 1; l >= 0 && low_area > 0; --l, --low_area)
visit[l] = 1;
}
else {
break;
}
}
// 내리막인 경우
else if (differ > 0) { // j부터 낮은 지대이다.
low_area = 0;
for (int l = j; l < N; ++l) {
if (visit[l] || map[i][l] != map[i][j]) break;
++low_area;
}
if (low_area >= L) { // 다리놓을 공간이 충분하므로 L개만큼 방문 표시하자
low_area = L;
for (int l = j; l < N && low_area > 0; ++l, --low_area)
visit[l] = 1;
}
else break;
}
// break되지 않고 여기까지왔다면 갈 수 있는 길임
if (j == N - 1) ++ret;
}
memset(visit, 0, sizeof(visit));
// 세로 검사
for (int j = 1; j < N; ++j) {
differ = map[j - 1][i] - map[j][i];
if (abs(differ) > 1) break; // 차이가 2 이상이면 갈 수 있는 길이 아님
// 오르막인 경우
if (differ < 0) {
low_area = 0;
for (int l = j - 1; l >= 0; --l) { // j가 오르막이므로 j-1부터 본다.
if (visit[l] || map[l][i] != map[j - 1][i]) break;
++low_area;
}
if (low_area >= L) { // 다리놓을 공간이 충분하므로 L개만큼 방문 표시하자
low_area = L;
for (int l = j - 1; l >= 0 && low_area > 0; --l, --low_area)
visit[l] = 1;
}
else break;
}
// 내리막인 경우
else if (differ > 0) {
low_area = 0;
for (int l = j; l < N; ++l) { // j부터 낮은 지대임
if (visit[l] || map[l][i] != map[j][i]) break;
++low_area;
}
if (low_area >= L) { // 다리놓을 공간이 충분하므로 L개만큼 방문 표시하자
low_area = L;
for (int l = j; l < N && low_area > 0; ++l, --low_area)
visit[l] = 1;
}
else break;
}
// break되지 않고 여기까지왔다면 갈 수 있는 길임
if (j == N - 1) ++ret;
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
input();
cout << solve();
return 0;
}
개발 환경 : VS2019
질문, 지적 환영합니다.
'알고리즘 > 백준' 카테고리의 다른 글
[C++] 백준 15684 사다리 조작 (0) | 2020.05.25 |
---|---|
[C++] 백준 14891 톱니바퀴 (0) | 2020.05.25 |
[C++] 백준 15683 감시 (0) | 2020.05.20 |
[C++] 백준 14500 테트로미노 (0) | 2020.05.20 |
[C++] 백준 2206 벽 부수고 이동하기 (0) | 2020.05.19 |