[C++] 백준 14890: 경사로
0. 들어가며
https://www.acmicpc.net/problem/14890
백준에 등록되어있는 14890 문제이다.
여러 개의 길이 있을 때, 조건에 맞는 경사로를 놓을 수 있는지 확인하는 문제이다.
처음에는 2차원 맵으로 예시가 표현되어 있어서 세로 길에서 놓은 경사로 위치를 가로 길에서 고려해야하는 줄 알고 조금 헤매었다.
문제 표현만 이럴 뿐, 실제로는 모두 독립된 길로 풀면 되는 단순한 문제였다.
1. 문제조건
입력
- 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
출력
- 첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.
2. 문제해석
단순하게 조건에 맞추어 앞선 경로를 검증하거나 지나온 경로를 검증하는 알고리즘을 작성하면 된다.
1. 핵심 변수
입력을 받아서 저장할 'map_'과 이를 기반으로 경로로 나누어 저장한 'roads_'를 사용했다. 매 길을 검증할 때마다, 경사로가 놓인 위치를 체크하기 위해 'slope'변수를 선언해서 사용했다.
vector<vector<int>> map_;
vector<vector<int>> roads_;
vector<bool> slope(N, false);2. 입력 받기
역시나 입력받기부터 시작해보자. (모든 문제가 너무 비슷해서 다음부터는 생략을 할까 고민중이다...)
cin >> N;
cin >> L;
map_.resize(N, vector<int>(N, 0));
for (int i = 0; N > i; ++i) {
for (int j = 0; N > j; ++j) {
cin >> map_[i][j];
}
}3. 필요한 함수 목록
1. 경로 후보군 생성
2차원 벡터로 이루어진 map을 만들었으나, 우리는 개별 경로에 대해 조건을 탐색해야하기 때문에, 2*N 개의 경로로 나누어줄 것이다.
가로와 세로 방향으로 탐색하며 경로 후보들을 만들었다
void make_roads() {
roads_.reserve(2 * N);
for (int i = 0; N > i; ++i) {
vector<int> tmp;
tmp.reserve(N);
for (int j = 0; N > j; ++j) {
tmp.emplace_back(map_[i][j]);
}
roads_.emplace_back(tmp);
}
for (int j = 0; N > j; ++j) {
vector<int> tmp;
tmp.reserve(N);
for (int i = 0; N > i; ++i) {
tmp.emplace_back(map_[i][j]);
}
roads_.emplace_back(tmp);
}
}2. 경로 조건 필터링
핵심이 되는 파트이다.
우선 조건을 잘 분리하여 정리한다. 크게 3 가지이다.
- 다음 블럭과의 높이차이가 1을 초과하는 경우 경사로를 놓을 수 없다.
- 다음 블럭이 1만큼 더 낮은 경우 L만큼의 경사로를 놓아야 하는데, 경사로를 놓는 동안 높이는 같아야 한다.
- 다음 블럭이 1만큼 더 높은 경우 지나온 경로에 경사로를 놓아야 하는데, L거리만큼 동일한 높이일 때만 놓을 수 있다.
추가로, 당연히 검사해야하는 길이가 L 보다 적은 경우에는 어차피 놓을 수 없으므로 후보에서 제거한다.
경사로를 놓은 곳은 다시 놓을 수 없으므로, slope 변수를 통해 표시해주었다.
예외처리 (L=1인 경우)가 필요한 점에 유의해야 하며, 다음 블럭이 높은 경우에만 경사로가 놓인 위치를 검사하면 된다. (반대의 경우는 앞으로 경사로를 놓기만 할 것이므로.)
void build_slope(const vector<int>& road) {
vector<bool> slope(N, false);
for (int i = 0; road.size() - 1 > i; ++i) {
// 다음 블럭과의 높이차 계산
int diff = road[i] - road[i + 1];
if (fabs(diff) > 1) {
// 높이차가 1 초과라 경사로를 놓을 수 없음
return;
} else if (diff == 0) {
} else if (diff == 1) {
// 남은 거리가 최소 기준을 만족하는지 확인
if (i + L < N) {
// 현재 블럭의 다음 블럭과 그 다음 블럭들을 확인해야함
for (int x = 1; x < L; ++x) {
if (road[i + x] != road[i + 1 + x]) {
// L 동안 같지않은 경우가 있으면 실패
return;
} else {
slope[i + x] = true;
slope[i + 1 + x] = true;
}
}
if (L == 1) {
slope[i + 1] = true;
}
} else {
// 경사로를 놓을 공간이 안남아있음
return;
}
} else if (diff == -1) {
// 지나온 거리가 최소 기준을 만족하는지 확인
if ((i + 1 - L) >= 0) {
// 현재 블럭과 이전 블럭들을 확인해야함
for (int x = 0; x < L - 1; ++x) {
if (road[i - x] != road[i - x - 1]) {
// L 동안 같지 않은 경우가 있으면 실패
return;
} else {
if (slope[i - x] == true || slope[i - x - 1] == true) {
// 이미 경사로가 있음
return;
}
// slope 설정할 필요가 없음의 유의!!!!!
// slope[i - x] = true;
// slope[i - x - 1] = true;
}
}
if (L == 1 && slope[i] == true) {
// 이미 경사로가 있음
return;
}
if (L == 1) {
slope[i] = true;
}
} else {
return;
}
}
// 가독성을 위해 else로 만들지 않고 조건 명시. 알고리즘 완결성을 위해서는 else가 있는게 좋음
}
++count;
}3. 결과
단순한 알고리즘이였으나, 조건을 잘 정립해야하는 문제였다.
