문제
크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.
오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.
다음과 같은 N=6인 경우 지도를 살펴보자.
이때, 길은 총 2N개가 있으며, 아래와 같다.
길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
- 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
- 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
- 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.
아래와 같은 경우에는 경사로를 놓을 수 없다.
- 경사로를 놓은 곳에 또 경사로를 놓는 경우
- 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
- 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
- 경사로를 놓다가 범위를 벗어나는 경우
L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.
경사로를 놓을 수 없는 경우는 아래와 같다.
위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.
가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 파란색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.
지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
출력
첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.
풀이
2차원 배열을 가로와 세로로 한줄씩 읽어들이면서 길이 될 수 있는지 체크해 보며 풀면된다.
경사로는 항상 칸의 높이가 바뀌는 경우에만 생긴다. 우선 이 칸의 높이차가 2이상이면 무조건 경사로를 놓을 수 없어서 false이다
칸의 길이가 바뀌는 시점의 index를 모두 vector cut_idx에 저장한다. 예를 들어 1 2 2 3 3 4 의 경우 cut_idx는 {1,3,5} 이 된다.
이렇게 구한 각 vector의 iteration을 끝까지 돌면서 그 시점에 경사로를 놓을 수 있는지 없는지 판단한다.
판단할때에는 두가지 경우가 존재한다.
1. 낮은길에서 높은길로 변했던 건지
2. 높은길에서 낮은길로 변했던 건지
우선 낮은길에서 높은길로 변했다는 것은 경사로를 왼쪽에 놓아야 한다는 것이다. 이때는 왼쪽 길의 길이가 L보다 크기만 하면 경사로를 놓을 수 있다.
그림에서 왼쪽 길의 길이는 cut_idx[i]-cut_idx[i-1]이 된다. 따라서 cut_idx[i]-cut_idx[i-1] >= L이면 통과 아니면 false가 된다.
반면 높은길에서 낮은길로 변했다는 것은 경사로를 왼쪽 길이 아닌 현재 길에 놓아야 한다는 것이다. 즉 이경우는 cut_idx[i+1] - cut_idx[i]의 길이를 봐야한다. 이때 두가지 케이스가 있다.
1번 case는 그림과 같이 길이 높은칸 두개로 둘러쌓인 경우이다. 이 경우에는 현재 길에 경사로를 두개를 놓아야 한다. 따라서 vector[i+1]-vector[i]가 2L 이상이어야 한다.
2번 case는 그림과 같이 되어있는 것이다. 이때는 경사로를 하나만 놔도 되기 때문에 vector[i+1]-vector[i]가 L 이상이면 된다.
이렇게 cut_idx를 모두 돌아서 return false에 걸리지 않고 모두 통과하면 return true가 되어 count를 ++해주고 최종적인 count를 출력해준다.
#include <iostream>
#include <vector>
using namespace std;
int N, L;
vector<vector<int>>Map;
void input() {
cin >> N >> L;
for (int i = 0; i < N; ++i) {
vector<int>in;
for (int j = 0; j < N; ++j) {
int num;
cin >> num;
in.push_back(num);
}
Map.push_back(in);
}
}
bool Load(vector<int>l) {
int tmp = l[0];
vector<int>cut_idx;
for (int i = 1; i < l.size(); ++i) {
if (l[i] != tmp) {
tmp = l[i];
cut_idx.push_back(i);
}
}
int tmp_idx = 0;
for (int i = 0; i < cut_idx.size(); ++i) {
if (l[tmp_idx] - l[cut_idx[i]] >= 2 || l[tmp_idx] - l[cut_idx[i]] <= -2) {
return false;
}
if (l[tmp_idx] > l[cut_idx[i]]) {
if (i == cut_idx.size() - 1) {
if (l.size() - cut_idx[i] < L) {
return false;
}
}
else {
if (l[cut_idx[i + 1]] > l[cut_idx[i]]) {
if (cut_idx[i + 1] - cut_idx[i] < 2 * L) {
return false;
}
}
else {
if (cut_idx[i + 1] - cut_idx[i] < L) {
return false;
}
}
}
}
else {
if (cut_idx[i] - tmp_idx < L) {
return false;
}
}
tmp_idx = cut_idx[i];
}
return true;
}
void output() {
int tmp = 0;
for (int i = 0; i < N; ++i) {
vector<int>load = Map[i];
if (Load(load)) {
++tmp;
}
}
for (int i = 0; i < N; ++i) {
vector<int>load;
for (int j = 0; j < N; ++j) {
load.push_back(Map[j][i]);
}
if (Load(load)) {
++tmp;
}
}
cout << tmp;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
output();
}