(백준 14890번) 경사로
문제 설명
크기가 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보다 작거나 같은 자연수이다.
출력
첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.
문제 풀이
생각할 부분이 많지만 하나씩 차근차근 구현하면 크게 어렵지 않은 시뮬레이션 문제였다. 이 문제에서 생각해봐야 할 점은 두 가지이다. 첫째는 경사로의 방향이다. 행렬을 탐색하던 도중 단차를 만나면 경사로를 깔 수 있는지의 연산을 해야하는데, 단차가 더 높은 단차인지 더 낮은 단차인지에 따라 경사로의 방향이 달라지고 탐색해야할 범위도 달라진다. 높은 단차를 만났다면 현재 위치 이전의 l만큼의 구역을 탐색하면 되고, 낮은 단차를 만났다면 현재 위치를 포함해서 l만큼의 구역을 탐색하면 된다.
두 번째는 경사로를 이미 깔은 위치에는 경사로를 다시 깔 수 없다는 것이다. 예를 들어 3 3 2 2 3 3과 같은 줄에서는 경사로를 두 번 깔아야 지나갈 수 있으므로 이는 지나갈 수 없는 길이 된다. 이것에 대해서는 bfs 등에서 자주 쓰는 visited 배열을 활용하여 이 위치에 경사로를 깔았는지를 표시해주면 된다.
보통 길을 탐색할 때 이 길을 지나갈 수 없는 조건들을 체크하여 연산하게 될텐데, 위에서 본 두 가지 구현점을 감안해서 생각해보면 길을 지나갈 수 없는 조건은 {단차가 1보다 큰 경우, 경사로를 깔아야하는데 범위를 벗어난 경우, 경사로를 깔아야하는데 이미 그 자리에 경사로가 깔린 경우, 경사로를 깔아야하는데 l만큼 연속하지 않은 경우}가 된다. 이 조건들을 체크하며 행렬을 침착하게 탐색해나가면 풀 수 있을 것이다. 자세한 코드는 다음과 같다.
코드
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,l;
bool oob(int x, int y) {
if(x<n && x>=0 && y<n && y>=0) return true;
return false;
}//범위를 벗어났는지 탐색하는 함수
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n >> l;
int table[105][105];
int count=0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cin >> table[i][j];
}
}
for(int i=0; i<n; i++) {
int cur=0; int built[n]={0,};//경사로가 깔렸는지 표시하는 배열
for(int j=0; j<n; j++) {
if(cur==0) cur=table[i][j];
if(table[i][j]==cur-1) {
bool flag=false;
for(int k=j; k<j+l; k++) {
if(!oob(i,k) || table[i][k]!=table[i][j] || built[k]) {
flag=true; break;
}//범위를 벗어났거나, 연속하지 않거나, 경사로가 이미 있거나
else built[k]=1;
}//낮은 단차이므로 현재를 포함해서 l만큼 탐색
if(flag) break;
else cur=table[i][j];
}
else if(table[i][j]==cur+1) {
bool flag=false;
for(int k=j-1; k>=j-l; k--) {
if(!oob(i,k) || cur!=table[i][k] || built[k]) {
flag=true; break;
}
else built[k]=1;
}
if(flag) break;
else cur=table[i][j];
}//높은 단차이므로 현재 이전부터 l만큼 탐색
else if(cur==table[i][j]) {}
else break;//단차가 1보다 크면 break
if(j==n-1) count++;//무사히 끝까지 도착하면 count를 가산
}
}
for(int i=0; i<n; i++) {//여기서부턴 행이 아닌 열의 계산이므로
//i와 j, i와 k의 위치만 바꿔 위의 연산을 그대로 사용하면 된다.
int cur=0; int built[n]={0,};
for(int j=0; j<n; j++) {
if(cur==0) cur=table[j][i];
if(table[j][i]==cur-1) {
bool flag=false;
for(int k=j; k<j+l; k++) {
if(!oob(k,i) || table[k][i]!=table[j][i] || built[k]) {
flag=true; break;
}
else built[k]=1;
}
if(flag) break;
else cur=table[j][i];
}
else if(table[j][i]==cur+1) {
bool flag=false;
for(int k=j-1; k>=j-l; k--) {
if(!oob(k,i) || cur!=table[k][i] || built[k]) {
flag=true; break;
}
else built[k]=1;
}
if(flag) break;
else cur=table[j][i];
}
else if(cur==table[j][i]) {}
else break;
if(j==n-1) count++;
}
}
cout << count;
}