[SWEA] 4014번 활주로 건설

4014번 활주로 건설

문제 링크

 

해결방법

주어진 조건을 구현하는 시뮬레이션 문제이다

삼성 기출문제인 경사로 문제와 동일하다

다시 푸는 문제지만 너~무 어렵다 정말…ㅠㅠㅠ

나중에 다시 풀어봐야지….퓨ㅠ

 

 

⭐️ 솔루션 ⭐️

경사로를 설치할 수 있는지 검사하는 여부가 까다롭다

• 높이 차가 1인가
• 이미 경사로가 설치되어 있는가
• 경사로가 맵 밖을 벗어나는가
• 경사로 설치 지형의 높이가 동일한가

또한 두 지형을 비교해 높이가 더 작은 쪽에 경사로를 설치해야한다

 

문제 조건

• 경사로는 겹치면 안됨
• 경사로가 맵 밖을 벗어나면 안됨
• x : 경사로의 길이 (높이 : 1)

 

 

소스코드

문제 해결 시간 : 1h 30m

메모리 : 12488 KB

시간 : 7 ms

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int testcase;
int n,x,ans;
int map[21][21];
bool chk[2][21][21];

void chkRow(){
    for(int j=0; j<n; j++){
        bool possible = true;
        
        for(int i=0; i<n-1; i++){
            int u = map[i][j];
            int d = map[i+1][j];
            int dif = abs(u-d);
            
            // 지형의 높이가 같다면
            if(dif == 0) continue;
            
            // 높이 차가 1보다 크다면
            if(dif > 1){
                possible = false;
                break;
            }
            
            // 아래쪽에 설치
            if(u > d){
                // 경사로 설치 가능 확인
                for(int k=i+1; k<=i+x; k++){
                    // 범위를 벗어났거나 이미 방문했거나 값이 다르면
                    if(k >= n || chk[0][k][j] || map[k][j] != d){
                        possible = false;
                        break;
                    }
                }
                
                // 경사로 설치
                if(possible){
                    for(int k=i+1; k<=i+x; k++){
                        chk[0][k][j] = true;
                    }
                }
            }
            // 위쪽에 설치
            else if(u < d){
                // 경사로 설치 가능 확인
                for(int k=i-1; k>i-x; k--){
                    // 범위를 벗어났거나 이미 방문했거나 값이 다르면
                    if(k < 0 || chk[0][k][j] || map[k][j] != u){
                        possible = false;
                        break;
                    }
                }
                
                // 경사로 설치
                if(possible){
                    for(int k=i-1; k>i-x; k--){
                        chk[0][k][j] = true;
                    }
                }
            }
            
        }
        
        if(possible) ans++;
    }
}

void chkCol(){
    for(int i=0; i<n; i++){
        bool possible = true;
        
        for(int j=0; j<n-1; j++){
            int l = map[i][j];
            int r = map[i][j+1];
            int dif = abs(l - r);
            
            // 지형의 높이가 같다면
            if(dif == 0) continue;
            
            // 높이 차가 1보다 크다면
            if(dif > 1){
                possible = false;
                break;
            }
            
            // 오른쪽에 설치
            if(l > r){
                // 경사로 설치 가능 확인
                for(int k=j+1; k<=j+x; k++){
                    // 범위를 벗어났거나 이미 방문했거나 값이 다르면
                    if(k>=n || chk[1][i][k] || map[i][k] != r){
                        possible = false;
                        break;
                    }
                }
                
                // 경사로 설치
                for(int k=j+1; k<=j+x; k++){
                    chk[1][i][k] = true;
                }
            }
            // 왼쪽에 설치
            else if(l < r){
                // 경사로 설치 가능 확인
                for(int k=j-1; k>j-x; k--){
                    // 범위를 벗어났거나 이미 방문했거나 값이 다르면
                    if(k>=n || chk[1][i][k] || map[i][k] != l){
                        possible = false;
                        break;
                    }
                }
                
                // 경사로 설치
                for(int k=j-1; k>j-x; k--){
                    chk[1][i][k] = true;
                }
            }
        }
        
        if(possible) ans++;
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int tc=1; tc<=testcase; tc++){
        cin >> n >> x;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> map[i][j];
            }
        }
        
        memset(chk, false, sizeof(chk));
        ans = 0;
        chkRow();
        chkCol();
        
        cout << "#" << tc << " " << ans << "\n";
    }
    
    return 0;
}