[SIM] 14890번 경사로

14890번 경사로

 

https://www.acmicpc.net/problem/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보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

 

예제 입력

6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2

6 2
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

6 3
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

6 1
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

 

예제 출력

3

7

3

11

 

해결방법

뭔가 어려워 보이는 단순 구현 시뮬레이션 문제이다

 

 

⭐️ 솔루션 ⭐️

행 열 의 모든 길에 대해서 길을 건널 수 있는지 확인해야한다

주어진 조건은 이러하다

• 경사로는 낮은 칸에만 설치 할 수 있다 (낮은칸은 연속된 L개)
• 높이차이는 1
• 맵 밖으로 설치 할 수 없음
• 한 노드에는 오직 하나의 경사로만 존재함

 

for문을 돌며 0 ~ n-1 행, 열 에 대해 길을 건널 수 있는지 확인해야한다

아래의 길이 있다고 가정해보자

3 2 2 1 1 1		//  N = 6 , M = 3

for문을 0 ~ n-2 의 인덱스에 대해서 반복한다

만약 해당 노드의 오른쪽에 있는 노드가 같지 않다면 경사로를 설치할 수 있는지 확인해본다

둘 중 작은 수를 찾은 뒤 해당 노드라면 왼쪽으로, 오른쪽 노드라면 오른쪽으로 경사로를 체크한다

만약 범위를 벗어나거나 이미 경사로가 설치되있거나 값이 같지 않다면 경사로를 설치할 수 없다

 

정리해보자면 전체적인 흐름은 다음과 같다

1. 길을 지나면서 다음 노드와 값이 같지 않다면 경사로 설치를 확인한다
2. 두 노드의 값 중, 작은 값의 방향으로 경사로 설치 가능 여부를 확인한다
3. 만약 맵을 벗어나거나 이미 설치되어있거나 값이 같지 않다면 경사로를 설치할 수 없다
4. 조건을 모두 만족한다면 경사로를 설치하고 다음 노드로 넘어간다

 

이러한 흐름을 총 2*N 번 수행하여 답을 구할 수 있다

아!! 그리고 처음에는 조건에 맞지 않다면 함수에서 return 을 하였는데 결과가 잘 나오지 않았다

모든 예외를 다룰 수 없기 때문에 가능하면 flag 변수를 둬서 마지막에 플래그 체크 후 값을 증가시키는 편이 더 정확할 수 있다

 

 

 

소스코드

문제 해결 시간 : 4h

메모리 : 2048 KB

시간 : 0 ms

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 101
#define INF 987654321
using namespace std;

/*
 
 - 경사로는 낮은 칸에만 놓을 수 있음 (낮은칸은 연속된 L개)
 - 높이차는 1
 - 범위를 벗어날 수 없음
 - 같은 곳에는 오직 하나의 경사로만 존재
 
 */

typedef pair<int, int> node;

int n,m,ans;
int map[MAX][MAX];
bool visited[MAX][MAX][2];  // 0 : 행 , 1 : 열

vector<node> v;

// 행 탐색
void goRow(int col){
    bool flag = true;
    
    // 0 ~ n-1 의 열을 돌며 탐색
    for(int i=0; i<n-1; i++){
        int u = map[i][col];
        int d = map[i+1][col];
        int dif = abs(u-d);
        
        // 노드가 같다면
        if(dif == 0) continue;
        
        // 높이 차가 1보다 크다면
        if(dif > 1){
            flag = false;
            break;
        }
        
        // 위쪽이 더 작은 노드라면
        else if(u < d){
            // 현재 노드부터 위쪽으로 이동하여 연속적인 L개의 낮은 노드가 존재한다면
            for(int j=i; j>i-m; j--){
                
                // 범위를 벗어났거나 이미 방문했거나 값이 다르다면
                if(j < 0 || visited[j][col][0] || map[j][col] != u){
                    v.clear();
                    flag = false;
                    break;
                }
                
                v.push_back(node(j,col));
            }
        }
        // 아래쪽이 더 작은 노드라면
        else{
            // 현재 노드부터 아래쪽으로 이동하여 연속적인 L개의 낮은 노드가 존재한다면
            for(int j=i+1; j<i+1+m; j++){
                
                // 범위를 벗어났거나 이미 방문했거나 값이 다르다면
                if(j >= n || visited[j][col][0] || map[j][col] != d){
                    v.clear();
                    flag = false;
                    break;
                }
                
                v.push_back(node(j,col));
            }
        }
        
        if(flag){
            // 경사로 설치
            for(int j=0; j<v.size(); j++){
                visited[v[j].first][v[j].second][0] = true;
            }
            v.clear();
        }else{
            break;
        }
    }
    
    if(flag)
        ans++;
}

// 열 탐색
void goCol(int row){
    bool flag = true;
    
    // 0 ~ n-1 의 행을 돌며 탐색
    for(int i=0; i<n-1; i++){
        int l = map[row][i];
        int r = map[row][i+1];
        int dif = abs(l-r);
        
        // 노드가 같다면
        if(dif == 0) continue;
        
        // 높이 차가 1보다 크다면
        if(dif > 1){
            flag = false;
            break;
        }
        
        // 왼쪽이 더 작은 노드라면
        else if(l < r){
            // 현재 노드부터 왼쪽으로 이동하여 연속적인 L개의 낮은 노드가 존재한다면
            for(int j=i; j>i-m; j--){
                
                // 범위를 벗어났거나 이미 방문했거나 값이 다르다면
                if(j < 0 || visited[row][j][1] || map[row][j] != l){
                    v.clear();
                    flag = false;
                    break;
                }
                
                v.push_back(node(row,j));
            }
        }
        // 오른쪽이 더 작은 노드라면
        else{
            // 현재 노드부터 오른쪽으로 이동하여 연속적인 L개의 낮은 노드가 존재한다면
            for(int j=i+1; j<i+1+m; j++){
               
                // 범위를 벗어났거나 이미 방문했거나 값이 다르다면
                if(j >= n || visited[row][j][1] || map[row][j] != r){
                    v.clear();
                    flag = false;
                    break;
                }
                
                v.push_back(node(row,j));
            }
        }
        
        if(flag){
            // 경사로 설치
            for(int j=0; j<v.size(); j++){
                visited[v[j].first][v[j].second][1] = true;
            }
            v.clear();
        }else{
            break;
        }
    }
    
    if(flag)
        ans++;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }
    
    memset(visited, false, sizeof(visited));
    
    ans = 0;
    for(int i=0; i<n; i++){
        goRow(i);
        goCol(i);
    }
    
    cout << ans << "\n";
    
    return 0;
}