SWEA4014 [모의 SW 역량테스트] 활주로 건설 C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH&categoryId=AWIeW7FakkUDFAVH&categoryType=CODE&problemTitle=모의&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2 

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA4014.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA4014
//
//  Created by Hwayeon on 2021/10/16.
//

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

int N, X;
int area[20][20] = {0, };
int visit[20] = {0, };
int total_cnt = 0;

void find_route_row(){
    for(int r=0; r<N; r++){
        memset(visit, 0, sizeof(visit));
        bool check = true;
        int before = area[r][0];
        int cnt = 1;
        int c = 1;
        while(c < N){
            if(area[r][c] == before){
                cnt++;
                c++;
            }
            else if(abs(area[r][c]-before) >= 2){
                check = false;
                break;
            }
            else{
                //오르막길
                if(area[r][c] > before){
                    if(cnt < X){
                        check = false;
                        break;
                    }
                    for(int cc=c-X; cc<c; cc++){
                        if(visit[cc]){
                            check = false;
                            break;
                        }
                        visit[cc] = 1;
                    }
                    if(!check) break;
                    before = area[r][c];
                    cnt = 1;
                    c++;
                }
                //내리막길
                else{
                    if(c+X > N){
                        check = false;
                        break;
                    }
                    for(int cc=c; cc<c+X; cc++){
                        if(area[r][cc] == area[r][c]){
                            visit[cc] = 1;
                            continue;
                        }
                        check = false;
                        break;
                    }
                    if(!check) break;
                    before = area[r][c];
                    cnt = X;
                    c++;
                }
            }
        }
        if(check) total_cnt++;
    }
}

void find_route_col(){
    for(int c=0; c<N; c++){
        memset(visit, 0, sizeof(visit));
        bool check = true;
        int before = area[0][c];
        int cnt = 1;
        int r = 1;
        while(r < N){
            if(area[r][c] == before){
                cnt++;
                r++;
            }
            else if(abs(area[r][c]-before) >= 2){
                check = false;
                break;
            }
            else{
                //오르막길
                if(area[r][c] > before){
                    if(cnt < X){
                        check = false;
                        break;
                    }
                    for(int rr=r-X; rr<r; rr++){
                        if(visit[rr]){
                            check = false;
                            break;
                        }
                        visit[rr] = 1;
                    }
                    if(!check) break;
                    before = area[r][c];
                    cnt = 1;
                    r++;
                }
                //내리막길
                else{
                    if(r+X > N){
                        check = false;
                        break;
                    }
                    for(int rr=r; rr<r+X; rr++){
                        if(area[rr][c] == area[r][c]){
                            visit[rr] = 1;
                            continue;
                        }
                        check = false;
                        break;
                    }
                    if(!check) break;
                    before = area[r][c];
                    cnt = X;
                    r++;
                }
            }
        }
        if(check) total_cnt++;
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        total_cnt = 0;
        cin >> N >> X;
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                cin >> area[r][c];
            }
        }
        find_route_row();
        find_route_col();
        cout << "#" << test_case << " " << total_cnt << endl;
    }
    return 0;
}

---

풀이 과정

 

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

int N, X;
int area[20][20] = {0, };
int visit[20] = {0, };
int total_cnt = 0;

void find_route_row(){
    for(int r=0; r<N; r++){
    	//경사로 설치 여부를 체크하는 visit 배열 초기화
        memset(visit, 0, sizeof(visit));
        //check = true -> 활주로 설치 가능, check = false -> 활주로 설치 불가
        bool check = true;
        //이전 위치의 경사값
        int before = area[r][0];
        //이전 경사의 길이
        int cnt = 1;
        int c = 1;
        
        //한 행 탐색
        while(c < N){
        	//이전 경사값과 현재 경사값이 같은 경우,
            if(area[r][c] == before){
                cnt++;
                c++;
            }
            //이전 경사값과 현재 경사값의 차이가 2이상인 경우, 활주로 건설 불가
            else if(abs(area[r][c]-before) >= 2){
                check = false;
                break;
            }
            //이전 경사값과 현재 경사값의 차이가 1인 경우,
            else{
                //오르막길인 경우,
                if(area[r][c] > before){
                	//이전 경사의 길이가 X보다 적은 경우, 경사로 설치 불가 -> 활주로 설치 불가
                    if(cnt < X){
                        check = false;
                        break;
                    }
                    
                    for(int cc=c-X; cc<c; cc++){
                    	//이미 경사로가 설치되어있는 경우, 경사로 설치 불가 
                        if(visit[cc]){
                            check = false;
                            break;
                        }
                        //경사로 설치
                        visit[cc] = 1;
                    }
                    
                    //경사로 설치 불가인 경우 -> 활주로 설치 불가
                    if(!check) break;
                    
                    //경사로 설치 가능한 경우,
                    before = area[r][c];
                    cnt = 1;
                    c++;
                }
                //내리막길인 경우,
                else{
                	//경사로의 길이가 절벽지대를 벗어나는 경우, 경사로 설치 불가 -> 활주로 설치 불가
                    if(c+X > N){
                        check = false;
                        break;
                    }
                    
                    for(int cc=c; cc<c+X; cc++){
                        //같은 높이인 경우, 경사로 설치
                        if(area[r][cc] == area[r][c]){
                            visit[cc] = 1;
                            continue;
                        }
                        //다른 높이인 경우, 경사로 설치 불가
                        check = false;
                        break;
                    }
                    
                    //경사로 설치 불가인 경우 -> 활주로 설치 불가
                    if(!check) break;
                    
                    //경사로 설치 가능한 경우,
                    before = area[r][c];
                    cnt = X;
                    c++;
                }
            }
        }
        //활주로 설치 가능한 경우, total_cnt 카운팅
        if(check) total_cnt++;
    }
}

void find_route_col(){
    for(int c=0; c<N; c++){
    	//경사로 설치 여부를 체크하는 visit 배열 초기화
        memset(visit, 0, sizeof(visit));
        //check = true -> 활주로 설치 가능, check = false -> 활주로 설치 불가
        bool check = true;
        //이전 위치의 경사값
        int before = area[0][c];
        //이전 경사의 길이
        int cnt = 1;
        int r = 1;
        
        //한 열 탐색
        while(r < N){
        	//이전 경사값과 현재 경사값이 같은 경우,
            if(area[r][c] == before){
                cnt++;
                r++;
            }
            //이전 경사값과 현재 경사값의 차이가 2이상인 경우, 활주로 건설 불가
            else if(abs(area[r][c]-before) >= 2){
                check = false;
                break;
            }
            //이전 경사값과 현재 경사값의 차이가 1인 경우,
            else{
                //오르막길인 경우,
                if(area[r][c] > before){
                	//이전 경사의 길이가 X보다 적은 경우, 경사로 설치 불가 -> 활주로 설치 불가
                    if(cnt < X){
                        check = false;
                        break;
                    }
                    
                    for(int rr=r-X; rr<r; rr++){
                    	//이미 경사로가 설치되어있는 경우, 경사로 설치 불가
                        if(visit[rr]){
                            check = false;
                            break;
                        }
                        //경사로 설치
                        visit[rr] = 1;
                    }
                    //경사로 설치 불가인 경우 -> 활주로 설치 불가
                    if(!check) break;
                    
                    //경사로 설치 가능한 경우,
                    before = area[r][c];
                    cnt = 1;
                    r++;
                }
                //내리막길인 경우,
                else{
                	//경사로의 길이가 절벽지대를 벗어나는 경우, 경사로 설치 불가 -> 활주로 설치 불가
                	if(r+X > N){
                    	check = false;
                        break;
                    }
                    
                    for(int rr=r; rr<r+X; rr++){
                    	//같은 높이인 경우, 경사로 설치
                        if(area[rr][c] == area[r][c]){
                            visit[rr] = 1;
                            continue;
                        }
                        check = false;
                        break;
                    }
                    //경사로 설치 불가인 경우 -> 활주로 설치 불가
                    if(!check) break;
                    
                    //경사로 설치 가능한 경우,
                    before = area[r][c];
                    cnt = X;
                    r++;
                }
            }
        }
        //활주로 설치 가능한 경우, total_cnt 카운팅
        if(check) total_cnt++;
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        total_cnt = 0;
        cin >> N >> X;
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                cin >> area[r][c];
            }
        }
        find_route_row();
        find_route_col();
        cout << "#" << test_case << " " << total_cnt << endl;
    }
    return 0;
}
//시간복잡도 = O(N^2), 공간복잡도 = O(N^2)

---

오답노트

백준 14890번 경사로 문제와 똑같다.

1달 전에 경사로 문제를 풀었어서 그와 비슷하게 문제를 풀었는데 테스트케이스 47 언저리에서 자꾸 시간초과 또는 틀렸습니다가 나왔다..

 

다시 차근차근 풀어봤는데 마지막 테스트케이스에서 걸렸다... 도대체 왜일까 하고 아래 댓글을 살펴보니 격자 크기를 1 크게 하면 통과된다는 말이 있어서 제출해봤더니 진짜 통과가 되었다.

그런데 원인이 뭔지 모르겠어서 다시 코드를 살펴보니 한 가지 예외처리를 안한걸 발견했다..!

 

바로 내리막길인 경우 설치할 경사로가 영역 밖으로 벗어날 수 있다는 점이다.

코드를 짤때 이러한 엣지 경우를 꼭 체크하면서 짜도록 노력하자!!!

                //내리막길
                else{
                    //예외처리
                    //설치할 경사로가 절벽지대를 벗어날 수 있다
                    if(r+X > N){
                        check = false;
                        break;
                    }
                    for(int rr=r; rr<r+X; rr++){
                        if(area[rr][c] == area[r][c]){
                            visit[rr] = 1;
                            continue;
                        }
                        check = false;
                        break;
                    }
                    if(!check) break;
                    before = area[r][c];
                    cnt = X;
                    r++;
                }