백준 14890 경사로 C++

코테 노트/백준

백준 14890 경사로 C++

화요밍 2021. 1. 14. 21:38

728x90

www.acmicpc.net/problem/14890

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

최종 코드

GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ14890.cpp

//
//  main.cpp
//  BJ14890
//
//  Created by 최화연 on 2022/04/24.
//

#include <iostream>
using namespace std;

int N, L;
int map[100][100] = {0, };
int answer = 0;

void find_route_row() {
    //row에 대하여
    for (int r=0; r<N; r++) {
        int visits[100] = {0, };
        int c = 1;
        int before_h = map[r][0];
        int cnt = 1;
        bool check = true;
        while (c < N) {
            int differ = abs(map[r][c] - before_h);
            if (differ > 1) {
                check = false;
                break;
            }
            else if (differ == 0) cnt ++;
            else {
                //왼쪽에 경사로 설치
                if (map[r][c] > before_h) {
                    if (cnt < L) {
                        check = false;
                        break;
                    }
                    else {
                        //check visits
                        for (int l=1; l<=L; l++) {
                            int cc = c - l;
                            if (visits[cc]) {
                                check = false;
                                break;
                            }
                            visits[cc] = 1;
                        }
                        if (!check) break;
                        before_h = map[r][c];
                        cnt = 1;
                    }
                }
                //오른쪽에 경사로 설치
                else {
                    before_h = map[r][c];
                    for (int l=0; l<L; l++) {
                        int cc = c + l;
                        if (cc >= N || map[r][cc] != before_h) {
                            check = false;
                            break;
                        }
                        visits[cc] = 1;
                    }
                    if (!check) break;
                    if (c+L < N) {
                        if (before_h > map[r][c+L-1]) {
                            check = false;
                            break;
                        }
                    }
                    cnt = 0;
                    c += (L-1);
                }
            }
            c++;
        }
        
        if (check) {
            answer ++;
        }
    }
}

void find_route_col() {
    //col에 대하여
    for (int c=0; c<N; c++) {
        int visits[100] = {0, };
        int r = 1;
        int before_h = map[0][c];
        int cnt = 1;
        bool check = true;
        while (r < N) {
            int differ = abs(map[r][c] - before_h);
            if (differ > 1) {
                check = false;
                break;
            }
            else if (differ == 0) cnt ++;
            else {
                //위쪽에 경사로 설치
                if (map[r][c] > before_h) {
                    if (cnt < L) {
                        check = false;
                        break;
                    }
                    else {
                        //check visits
                        for (int l=1; l<=L; l++) {
                            int rr = r - l;
                            if (visits[rr]) {
                                check = false;
                                break;
                            }
                            visits[rr] = 1;
                        }
                        if (!check) break;
                        before_h = map[r][c];
                        cnt = 1;
                    }
                }
                //아래쪽에 경사로 설치
                else {
                    before_h = map[r][c];
                    for (int l=0; l<L; l++) {
                        int rr = r + l;
                        if (rr >= N || map[rr][c] != before_h) {
                            check = false;
                            break;
                        }
                        visits[rr] = 1;
                    }
                    if (!check) break;
                    if (r+L < N) {
                        if (before_h > map[r+L-1][c]) {
                            check = false;
                            break;
                        }
                    }
                    cnt = 0;
                    r += (L-1);
                }
            }
            r++;
        }

        if (check) {
            answer ++;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> L;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> map[i][j];
        }
    }
    
    find_route_row();
    find_route_col();
    
    cout << answer << endl;
    
    return 0;
}

풀이 과정

풀이 시간 51분

#include <iostream>
using namespace std;

int N, L;
int map[100][100] = {0, };
int answer = 0;

void find_route_row() {
    //row에 대하여
    for (int r=0; r<N; r++) {
        int visits[100] = {0, };
        int c = 1;
        int before_h = map[r][0];
        int cnt = 1;
        bool check = true;
        while (c < N) {
            int differ = abs(map[r][c] - before_h);
            if (differ > 1) {
                check = false;
                break;
            }
            else if (differ == 0) cnt ++;
            else {
                //왼쪽에 경사로 설치
                if (map[r][c] > before_h) {
                    if (cnt < L) {
                        check = false;
                        break;
                    }
                    else {
                        //check visits
                        for (int l=1; l<=L; l++) {
                            int cc = c - l;
                            if (visits[cc]) {
                                check = false;
                                break;
                            }
                            visits[cc] = 1;
                        }
                        if (!check) break;
                        before_h = map[r][c];
                        cnt = 1;
                    }
                }
                //오른쪽에 경사로 설치
                else {
                    before_h = map[r][c];
                    for (int l=0; l<L; l++) {
                        int cc = c + l;
                        if (cc >= N || map[r][cc] != before_h) {
                            check = false;
                            break;
                        }
                        visits[cc] = 1;
                    }
                    if (!check) break;
                    if (c+L < N) {
                        if (before_h > map[r][c+L-1]) {
                            check = false;
                            break;
                        }
                    }
                    cnt = 0;
                    c += (L-1);
                }
            }
            c++;
        }
        
        if (check) {
            answer ++;
        }
    }
}

void find_route_col() {
    //col에 대하여
    for (int c=0; c<N; c++) {
        int visits[100] = {0, };
        int r = 1;
        int before_h = map[0][c];
        int cnt = 1;
        bool check = true;
        while (r < N) {
            int differ = abs(map[r][c] - before_h);
            if (differ > 1) {
                check = false;
                break;
            }
            else if (differ == 0) cnt ++;
            else {
                //위쪽에 경사로 설치
                if (map[r][c] > before_h) {
                    if (cnt < L) {
                        check = false;
                        break;
                    }
                    else {
                        //check visits
                        for (int l=1; l<=L; l++) {
                            int rr = r - l;
                            if (visits[rr]) {
                                check = false;
                                break;
                            }
                            visits[rr] = 1;
                        }
                        if (!check) break;
                        before_h = map[r][c];
                        cnt = 1;
                    }
                }
                //아래쪽에 경사로 설치
                else {
                    before_h = map[r][c];
                    for (int l=0; l<L; l++) {
                        int rr = r + l;
                        if (rr >= N || map[rr][c] != before_h) {
                            check = false;
                            break;
                        }
                        visits[rr] = 1;
                    }
                    if (!check) break;
                    if (r+L < N) {
                        if (before_h > map[r+L-1][c]) {
                            check = false;
                            break;
                        }
                    }
                    cnt = 0;
                    r += (L-1);
                }
            }
            r++;
        }

        if (check) {
            answer ++;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> L;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> map[i][j];
        }
    }
    
    find_route_row();
    find_route_col();
    
    cout << answer << endl;
    
    return 0;
}

이전 풀이

풀이 시간 1시간 10분

단순 구현 문제였다. 예전에 이 문제 봤을 때 어려웠던 기억이 남아있었는데, 결국 문제를 풀어냈는지 아닌지는 기억이 나지 않았다.

무튼 어려웠었던 기억이 있었기에 마음 단단히 먹고 문제를 풀어나갔는데, 의외로 쉬웠다...! 뭐지??,,

블로그에 그 당시에 문제 풀이를 기록했는지 보려고 검색해보니 1월에 풀었었던 문제였다.

벌써 8개월이나 지났기 때문에 잊어버렸는데 기록을 해두니 다시 볼 수 있어서 좋다!! 앞으로도 꾸준히 정리해 나가야겠당

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

int map[100][100] = {0, };
int visit[100] = {0, };
int road = 0;
int N, L;

void check_road(){
	//(1)각 행에 대하여 길을 탐색한다
    for(int r=0; r<N; r++){
    	//1. 해당 길의 경사로 설치 여부를 담는 visit배열 초기화
        memset(visit, 0, sizeof(visit));
        
        //길이라면 check = true, 아니면 check = false 
        int check = true;
        
        //이전 칸의 높이를 담는 before
        //첫 칸의 높이를 before로 초기화
        int before = map[r][0];
        
        //이전에 같은 높이를 갖는 칸들의 수를 카운팅하는 cnt
        //cnt가 L보다 크거나 같은 경우, 경사로를 설치할 수 있다
        int cnt = 1;
        
        //2. 두번째 칸부터 마지막 칸까지 탐색하여 최종적으로 해당 row가 길이 될 수 있는지 판단한다
        int c = 1;
        while(c < N){
        	//a. 이전 칸과 높이가 같은 경우, cnt 카운팅하고 다음 칸을 탐색한다
            if(map[r][c] == before){
                cnt ++;
                c ++;
                continue;
            }
            
            //b. 이전 칸과 현재 칸의 높이 차이가 2 이상인 경우, 해당 row는 길이 될 수 없으므로 while문을 빠져나온다.
            else if(abs(map[r][c] - before) > 1){
                check = false;
                break;
            }
            
            //c. 높이 차이가 1인 경우, 경사로를 설치할 수 있는지를 판별한다
            else{
                //c-1. 오르막길 인 경우, 이전 칸에 길이가 L인 경사로를 놓아야한다
                if(map[r][c] - before == 1){
                    //길이가 L인 경사로를 놓을 수 있는 경우,
                    if(cnt >= L){
                        for(int cc=c-L; cc<c; cc++){
                            //이미 경사로가 설치되어 있는 경우, 설치 불가 -> 길이 아니므로 while문 빠져나온다
                            if(visit[cc]){
                                check = false;
                                break;
                            }
                            //경사로를 설치한다
                            visit[cc] = 1;
                        }
                        //경사로 설치 완료, 현재 칸의 위치를 before로 설정하고 cnt를 1로 초기화한 후, 다음 칸을 탐색한다
                        before = map[r][c];
                        cnt = 1;
                        c ++;
                        continue;
                    }
                    
                    //길이가 L인 경사로를 놓을 수 없는 경우, 길이 아니므로 while문을 빠져나온다
                    else{
                        check = false;
                        break;
                    }
                }
                
                //c-2. 내리막길인 경우, 이후 칸들에 길이가 L인 경사로를 놓아야한다
                else{
                	//이후의 L칸에 경사로를 설치 할 수 있는지 탐색한다
                    int cc;
                    for(cc=c+1; cc<c+L; cc++){
                        if(map[r][cc] == map[r][c]) continue;
                        check = false;
                        break;
                    }
                    
                    //길이가 L인 경사로를 놓을 수 없는 경우, while문을 빠져나간다
                    if(!check) break;
                    
                    //경사로를 놓을 수 있는 경우, 경사로를 설치한다
                    for(cc=c; cc<c+L; cc++){
                        visit[cc] = 1;
                    }
                    before = map[r][c];
                    cnt = L;
                    c++;
                    continue;
                }
            }
        }
        //길이 맞는 경우 road 카운팅
        if(check) {
            road++;
        }
    }
    
    //(2)각 열에 대하여 길을 탐색한다 -> (1)과정을 col에 대해 진행한다
    for(int c=0; c<N; c++){
        memset(visit, 0, sizeof(visit));
        int check = true;
        int before = map[0][c];
        int cnt = 1;
        int r = 1;
        while(r < N){
        	//이전 칸과 높이가 같은 경우,
            if(map[r][c] == before){
                cnt ++;
                r ++;
                continue;
            }
            
            //높이 차이가 2 이상인 경우, 길이 아니다
            else if(abs(map[r][c] - before) > 1){
                check = false;
                break;
            }
            
            //높이 차이가 1인 경우,
            else{
                //오르막길 인 경우,
                if(map[r][c] - before == 1){
                    //경사로를 놓을 수 있는 경우,
                    if(cnt >= L){
                        for(int rr=r-L; rr<r; rr++){
                            //이미 경사로가 설치되어 있는 경우, 설치 불가 -> 길이 아니다
                            if(visit[rr]){
                                check = false;
                                break;
                            }
                            visit[rr] = 1;
                        }
                        //경사로 설치 완료
                        before = map[r][c];
                        cnt = 1;
                        r ++;
                        continue;
                    }
                    //경사로를 놓을 수 없는 경우, 길이 아니다
                    else{
                        check = false;
                        break;
                    }
                }

                //내리막길 인 경우,
                else{
                    int rr;
                    for(rr=r+1; rr<r+L; rr++){
                        if(map[rr][c] == map[r][c]) continue;
                        check = false;
                        break;
                    }
                    if(!check) break;
                    //경사로를 놓을 수 있는 경우, 경사로 설치
                    for(rr=r; rr<r+L; rr++){
                        visit[rr] = 1;
                    }
                    before = map[r][c];
                    cnt = L;
                    r++;
                    continue;
                }
            }
        }
        //길이 맞는 경우 road 카운팅
        if(check) {
            road++;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> L;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> map[i][j];
        }
    }
    check_road();
    cout << road << endl;
    return 0;
}
//시간복잡도 = O(N^2), 공간복잡도 = O(N^2)

풀이 시간 2시간 55분

//
//  main.cpp
//  BJ14890
//
//  Created by Hwayeon on 2021/01/12.
//
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int road[100][100];
int N, L;

int find_road_row(){
    vector<pair<int,int> > q;
    int row_road = 0;
    for(int row=0; row<N; row++){
        q.clear();
        bool visit[100] = {false,};
        q.push_back(make_pair(row, 0));
        int col = 1;
        while(col < N){
            if(road[row][col] == road[q.back().first][q.back().second]){
                q.push_back(make_pair(row, col));
                col++;
            }
            else if(road[row][col] > road[q.back().first][q.back().second]){
                if(abs(road[row][col] - road[q.back().first][q.back().second]) == 1){
                    if(q.size()>=L){
                        bool check = true;
                        for(int i=1; i<=L; i++){
                            int now_col = q[q.size()-i].second;
                            if(visit[now_col]==true) check = false;
                        }
                        if(check == false) break;
                        else{
                            q.clear();
                            q.push_back(make_pair(row, col));
                            col++;
                        }
                    }
                    else break;
                }
                else break;
            }
            else{
                if(abs(road[row][col] - road[q.back().first][q.back().second]) == 1){
                    bool check = true;
                    for(int i=col; i<col+L; i++){
                        if(road[row][i] != road[row][col]) check = false;
                    }
                    if(check == false) break;
                    else{
                        q.clear();
                        for(int i=col; i<col+L; i++){
                            visit[i] = true;
                        }
                        q.push_back(make_pair(row, col+L-1));
                        col = col+L;
                    }
                }
                else break;
            }
        }
        if(col == N) {
            row_road++;
        }
    }
    return row_road;
}

int find_road_col(){
    int col_road = 0;
    vector<pair<int,int> > q;
    for(int col=0; col<N; col++){
        q.clear();
        bool visit[100] = {false,};
        q.push_back(make_pair(0, col));
        int row = 1;
        while(row < N){
            if(road[row][col] == road[q.back().first][q.back().second]){
                q.push_back(make_pair(row, col));
                row++;
            }
            else if(road[row][col] > road[q.back().first][q.back().second]){
                if(abs(road[row][col] - road[q.back().first][q.back().second]) == 1){
                    if(q.size()>=L){
                        bool check = true;
                        for(int i=1; i<=L; i++){
                            int now_row = q[q.size()-i].first;
                            if(visit[now_row]==true) check = false;
                        }
                        if(check == false) break;
                        q.clear();
                        q.push_back(make_pair(row, col));
                        row++;
                    }
                    else break;
                }
                else break;
            }
            else{
                bool check = true;
                for(int i=row; i<row+L; i++){
                    if(road[i][col] != road[row][col]) check = false;
                }
                if(check == false) break;
                else{
                    q.clear();
                    for(int i=row; i<row+L; i++){
                        visit[i] = true;
                    }
                    q.push_back(make_pair(row+L-1, col));
                    row = row+L;
                }
            }
        }
        if(row == N) {
            col_road++;
        }
    }
    return col_road;
}

int main(int argc, const char * argv[]) {
    cin >> N >> L;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> road[i][j];
        }
    }
    cout << find_road_row()+find_road_col() << endl;
    return 0;
}

나는 이 문제를 가로 방향과 세로 방향으로 나누어 가로 방향의 경우 모든 열을 각각 탐색하고, 세로 방향의 경우 모든 행을 탐색하여 길의 개수를 구하였다.

1. 가로 방향 탐색 find_road_row()

가로 방향 탐색은 전체적으로 모든 열을 탐색해야 하기 때문에, for문을 통해 반복이 N번 이루어진다.

또한, 현재 row의 요소만큼 탐색해야 하므로, col < N일 때 while문이 실행되도록 하였다.

초기 설정

        q.clear();
        bool visit[100] = {false,};
        q.push_back(make_pair(row, 0));
        int col = 1;

vector q

vector q는 큐처럼 동작하는(FIFO, 선입선출) 벡터로, 현재 탐색하는 위치가 이전에 탐색한 칸의 높이와 같으면 현재위치(row, col)를 저장한다. q의 크기를 통해 경사로를 놓을 수 있는지를 판별하거나, 이전에 탐색한 위치의 높이와 현재 탐색하는 높이의 차이를 계산할 수 있다.

for문이 반복되면서 row값이 변하게 되면, 즉 새로운 길 탐색이 시작되면 q.clear() 해준다.

또한 탐색이 시작되는 칸, 즉 row의 첫번째 요소를 q에 push 해준다.

visit

visit을 통해 row의 각 요소에 경사로가 설치되었는지 아닌지의 여부를 확인할 수 있다.

따라서, row값이 바뀌어 새로운 길 탐색이 시작될 때 visit 배열도 false로 초기화 해준다.

col = 1

row의 첫번째 요소를 q에 담아줬으므로, 두번째 요소부터 탐색을 시작하도록 col = 1로 초기화 해준다.

while문

while문을 통해 해당 row를 가로 방향으로 탐색해 나간다.

이때, 따져줘야할 조건은 크게 3가지가 있다.

1) 현재 칸이 이전 칸과 높이가 같은 경우

if(road[row][col] == road[q.back().first][q.back().second]){
                q.push_back(make_pair(row, col));
                col++;
            }

높이가 같은 경우가 연속될 경우에 경사로를 설치 할 수 있기 때문에, q에 현재 위치를 Push 해주고 다음 칸을 탐색한다.

2) 현재 칸이 이전 칸보다 높은 경우

else if(road[row][col] > road[q.back().first][q.back().second]){
    if(abs(road[row][col] - road[q.back().first][q.back().second]) == 1){
        if(q.size()>=L){
            bool check = true;
            for(int i=1; i<=L; i++){
                int now_col = q[q.size()-i].second;
                if(visit[now_col]==true) check = false;
            }
            if(check == false) break;
            else{
                q.clear();
                q.push_back(make_pair(row, col));
                col++;
            }
         }
         else break;
      }
      else break;
 }

[1] 현재 칸 - 이전칸 != 1인 경우

해당 row의 길은 지나갈 수 없으므로 break 해준다. (while문에서 벗어나 다음 row의 길 탐색한다.)

[2] 현재 칸 - 이전칸 = 1인 경우

- q.size() >= L인 경우, q에 저장된 연속된 칸을 뒤에서 부터 L개의 칸까지 경사로가 설치가 되어있는지를 체크한다.

check == true인 경우, L개의 칸들이 모두 경사로가 설치되어 있지 않으므로, 경사로를 설치하여 지나갈 수 있음을 의미한다. 이 후, q.clear() 한 후, 현재 위치를 q에 push 해주고 다음 행을 탐색한다.
check == false인 경우, L개의 칸 중 경사로가 설치되어 있는 칸이 있으므로, 경사로를 설치할 수 없으며 해당 row의 길을 건널 수 없다. 따라서, while문을 벗어나 다음 row의 길을 탐색하도록 한다.

- q.size() < L인 경우, 경사로의 길이 L보다 연속된 같은 높이의 칸의 수가 적으므로 경사로를 설치할 수 없다.

따라서, while문을 벗어나 다음 row의 길을 탐색하도록 한다.

3) 현재 칸이 이전 칸보다 낮은 경우

else{
    if(abs(road[row][col] - road[q.back().first][q.back().second]) == 1){
        bool check = true;
        for(int i=col; i<col+L; i++){
            if(road[row][i] != road[row][col]) check = false;
        }
        if(check == false) break;
        else{
            q.clear();
            for(int i=col; i<col+L; i++){
                visit[i] = true;
            }
            q.push_back(make_pair(row, col+L-1));
            col = col+L;
        }
     }
     else break;
 }

[1] 현재 칸 - 이전칸 != 1인 경우

해당 row의 길은 지나갈 수 없으므로 break 해준다. (while문에서 벗어나 다음 row의 길 탐색한다.)

[2] 현재 칸 - 이전칸 = 1인 경우

- 현재 칸부터 다음 연속된 칸까지의 L개의 칸에 경사로를 설치할 수있는지를 체크한다. 즉, 높이가 같은지를 확인한다.

check == true인 경우, L개의 칸에 경사로를 설치할 수 있으므로, q.clear() 한 후, visit[i] = true한다. 이 후, 현재 위치를 q에 push 해주고 L개 이후의 행을 탐색한다.
check == false인 경우, L개의 칸의 높이가 다르므로 경사로를 설치할 수 없어 해당 row의 길을 건널 수 없다. 따라서, while문을 벗어나 다음 row의 길을 탐색하도록 한다.

while문이 끝난 후, col == N이면 즉, 무사히 N개의 요소를 탐색했으면, 길을 지나갈 수 있음을 의미하므로 row_road++을 해준다.

2. 세로 방향 탐색 find_road_col()

세로 방향으로 탐색하는 것 또한 가로 방향 탐색과 같다. 이 때, 탐색하고자 하는 요소는 row가 된다.

3. 결과값 출력

가로 방향 탐색을 통해 반환된 row_road와 세로 방향 탐색을 통해 반환된 col_road를 더한 값이 최종 지나갈 수 있는 길의 수가 된다.

728x90

'코테 노트 > 백준' 카테고리의 다른 글

백준 13460 구슬 탈출 2 C++ (3)	2021.01.18
백준 14888 연산자 끼워넣기 C++ (0)	2021.01.17
백준 14502 연구소 C++ (0)	2021.01.11
백준 14503 로봇 청소기 C++ (0)	2021.01.11
백준 14889 스타트와 링크 C++ (0)	2021.01.06

현재글백준 14890 경사로 C++

Today :
Yesterday :

화요밍의 개발로그