[BOJ/백준 14890/C++] 경사로
https://www.acmicpc.net/problem/14890
14890번: 경사로
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
www.acmicpc.net
[문제 설명]
- N x N인 지도가 있고, 지도의 각 칸에는 그 곳의 높이가 적혀 있다.
- 이 지도에서 지나갈 수 있는 길이 몇개 있는지 구하여라.
- 길이란 한 행 또는 한 열 전부를 나타내면, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.
예시)
- 위 그림과 같이 N = 6인 지도가 있을 때 점선 사각형으로 나타낸 곳들이 길이다. 총 2N개가 있다.
- 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 같아야 한다. 또는 , 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
- 경사로는 낮은 칸에 놓이며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
- 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
- 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다,
아래와 같은 경우에는 경사로를 놓을 수 없다.
- 경사로를 놓은 곳에 또 경사로를 놓는 경우
- 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
- 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
- 경사로를 놓다가 범위를 벗어나는 경우
예를 들어 L = 2인 경우에 경사로를 놓을 수 있는 경우
경사로를 놓을 수 없는 경우
이와 같은 규칙을 적용하여 갈 수 있는 길을 확인해보면
파란색 사각형이 갈 수 있는 길, 빨간색 사각형이 갈 수 없는 길이다.
[문제 조건]
- 첫째 줄에 N ( 1 ≤ N ≤ 100 )과 L ( 1 ≤ L ≤ N )이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다.
- 각 칸의 높이는 10보다 작거나 같은 자연수이다.
- 시간 제한 : 2초
- 메모리 제한 : 512MB
[문제 풀이]
이 문제는 구현과 시뮬레이션만 잘 돌리면 풀 수 있는 문제다. 하지만 그게 쉽지않다.
일단 경우의 수를 나누어 한 번 생각해보자.
이 길을 갈 수 있는지 없는지 판정을 내릴 수 있는 때는 높이가 변화할때 판정을 내릴 수 있다.
L = 2라고 가정하자.
내려가는 경우나 올라가는 경우 둘다 높이 차이가 1보다 크면 어떠한 경우에도 이 길을 지나갈 수 없다. 따라서 높이가 1이상 차이나면 바로 break를 시켜서 탈출 하고, 만약 높이 차이가 -1인 경우(앞칸의 높이 - 다음칸의 높이)일 경우 올라가는 경우, 1인 경우는 내려가는 경우로 나눠서 생각한다.
- 먼저 -1인경우 ( 올라가는 경우 ) 전까지 같은 높이의 칸을 지나오면서 같은 높이의 칸의 개수를 same_cnt라는 변수를 이용해 개수를 세준다. 그 다음 높이가 변할때 L이랑 same_cnt를 비교하여 만약 L보다 same_cnt의 값이 더 작으면 경사로를 놓을 수 없으므로 break를 해주고 만약 같거나 크면 경사로를 놓을 수 있다는 뜻이니 계속 진행해주면 된다.
올라가는 경우는 그렇게 어렵지 않다. 하지만 내려가는 경우에 생각해야될 부분이 좀 많다.
- 내려가는 경우를 한번 생각해보자.
위 그림의 경우 L = 2라고 가정하자.
높이 3에서 2로 내려가는 경우 2가 총 L개 많큼 존재하다면 패스, 그렇지 않다면 break 한다.
여기서 2를 L개 만큼 세고 난 뒤에 index는 위 그림 기준 2번째 2를 가리키고 있을 것이다. 여기서 만약 다음칸의 높이가 2보다 큰 경우는 경사로의 길이에 상관없이 올라 갈 수 없다. ( 아래 그림 참고 )
그 다음 만약 다음칸이 같을 경우는 처음과 같이 same_cnt를 이용해 같은 높이의 칸의 개수를 세어주면된다.
마지막으로 바로 내려가는 경우 위의 방식을 다시 적용시켜주면된다. "높이 N에서 N-1로 내려가는 경우 N-1이 총 L개 많큼 존재하다면 패스, 그렇지 않다면 break 한다."
이런 방식들을 가로줄과 세로줄에 모두 적용시켜서 위의 조건들을 모두 통과해서 지나갈 수 있는 길이라고 판별되면 ans_cnt를 하나씩 증가시켜 정답을 구할 수 있다.
[소스 코드]
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>
using namespace std;
int n, l, ans_cnt=0;
vector<vector<int>> mp;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> l;
mp.resize(n);
for (int i = 0; i < n; i++) mp[i].resize(n);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { cin >> mp[i][j]; }
//가로길
for (int i = 0; i < n; i++)
{
int same_cnt = 1;
int prev_num = mp[i][0];
bool flag = true;
for (int j = 1; j < n; j++)
{
if (prev_num == mp[i][j]) same_cnt++;
else
{
int diff = prev_num - mp[i][j];
//prev_num이 더 클 경우 ( 내려가는 경우 )
if (diff == 1)
{
bool flag2 = true;
int k;
int tmp_cnt = 0, tmp = mp[i][j];
for (k = j; k < n; k++)
{
if (mp[i][k] == tmp) tmp_cnt++;
else { flag2 = false; break; }
if (tmp_cnt == l) break;
}
if (tmp_cnt != l) { flag = false; break; }
if (!flag2) { flag = false; break; }
else
{
j = k;
if (j + 1 < n)
{
if (mp[i][j] < mp[i][j + 1]) { flag = false; break; }
else if (mp[i][j] == mp[i][j + 1])
{
j++;
prev_num = mp[i][j];
same_cnt = 1;
}
else
{
prev_num = mp[i][j];
same_cnt = 1;
}
}
}
}
//prev_num이 더 작을 경우 ( 올라가는 경우 )
else if (diff == -1)
{
if (same_cnt >= l)
{
prev_num = mp[i][j];
same_cnt = 1;
}
else { flag = false; break; }
}
//높이가 2이상 차이나는 경우
else { flag = false; break; }
}
}
if (flag) ans_cnt++;
}
//세로길
for (int i = 0; i < n; i++)
{
int same_cnt = 1;
int prev_num = mp[0][i];
bool flag = true;
for (int j = 1; j < n; j++)
{
if (prev_num == mp[j][i]) same_cnt++;
else
{
int diff = prev_num - mp[j][i];
//prev_num이 더 클 경우 ( 내려가는 경우 )
if (diff == 1)
{
bool flag2 = true;
int k;
int tmp_cnt = 0, tmp = mp[j][i];
for (k = j; k < n; k++)
{
if (mp[k][i] == tmp) tmp_cnt++;
else { flag2 = false; break; }
if (tmp_cnt == l) break;
}
if (tmp_cnt != l) { flag = false; break; }
if (!flag2) { flag = false; break; }
else
{
j = k;
if (j + 1 < n)
{
if (mp[j][i] < mp[j+1][i]) { flag = false; break; }
else if (mp[j][i] > mp[j + 1][i])
{
prev_num = mp[j][i];
same_cnt = 1;
}
else
{
j++;
prev_num = mp[j][i];
same_cnt = 1;
}
}
}
}
//prev_num이 더 작을 경우 ( 올라가는 경우 )
else if (diff == -1)
{
if (same_cnt >= l)
{
prev_num = mp[j][i];
same_cnt = 1;
}
else { flag = false; break; }
}
//높이가 2이상 차이나는 경우
else { flag = false; break; }
}
}
if (flag) ans_cnt++;
}
cout << ans_cnt;
}
굳