ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 14890.경사로
    알고리즘/백준 BAEK JOON 2020. 5. 28. 03:04

    이번에 푼 문제는 백준 14890 경사로이다. 난이도는 쉬우나 문제를 보자마자 괜히 쫄았다.. => 고쳐야할점

     

    14890번: 경사로

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

    www.acmicpc.net

    그리고 분석시간을 충분히 가졌으나 실수를 하나 하는바람에 분명히 맞게구현했는데 시간을 낭비했다.

    찾아보니 나처럼 헤맨사람이 많았다. 이 문제에서 대부분 실수하는 부분은 경사로를 놓는 것에 있다.

    나는 경사로를 한 번 놓으면 치우지 않은 상태에서 다른 경로를 찾는건가 했는데... 아니였다..

    가로일 때 경사로 놔서 가능한 길 찾아보고 세로일 때 다시 경사로가 모두 없는 상태에서 찾는 것이었다..

    즉, 그냥 경사로를 놓아서 길이되면 그걸로 가능한 것이었다. 이래서 예제는 직접 손으로 확인하는게 최고다.

    이 문제는 그냥 구현하라는데로 구현하면 풀리는 단순한 문제이다.

    한 가지 그냥 간단한 스킬이 있다면 세로 배열 내용을 가로 배열로 바꿀 수 있다.

    int map[MAX][MAX] => 기본 배열
    int map2[MAX][MAX]=> 복사할 배열
    
    for(int i=0; i<n; i++){
    	for(int j=0; j<n; j++){
    		cin >> map[i][j];
            map2[j][i]=map[i][j];
    	}
    }

     

     

    < Code 설명 >

    #pragma warning(disable:4996)
    #include <iostream>
    #include <string.h>
    
    #define MAX 101
    
    using namespace std;
    
    int N, L;
    int map[MAX][MAX];
    int map2[MAX][MAX];
    
    bool ga_search(int y, int arr[MAX][MAX]){
    	int tmp = arr[y][0];
    	int cnt = 1;
    	bool jmp = false;
    	for (int i = 1; i < N; i++){
    		if (arr[y][i] == tmp) // 연속되면
    			cnt++; //숫자를 센다
    		else if (arr[y][i] != tmp){ // 다르면
                 // 높이차이가 1이나는지 확인
    			if (abs(arr[y][i] - tmp) == 1){ 
    				if (arr[y][i]>tmp){ // 오르막길에서
                         // 연속된 길이 경사로 길이만큼 앞에 존재한다면
    					if (cnt >= L)
    						cnt = 1; // cnt초기화 한다.
                            
    					else// 경사로 길이보다 cnt가 짧으면 종료
    						return false; 
    				}
    				else if (arr[y][i] < tmp){ // 내리막길에서
    					cnt = 0;
                        // 경사로를 놓을 수 있는지 확인 하는 변수
    					bool go = true; 
                        
                        //내리막길 발생지점이후 경사로확인
    					for (int z = i + 1; z < i + L; z++){ 
                            // 한번이라도 연속되지 않으면 경사로를 놓치못함
    						if (arr[y][i] != arr[y][z])
    							go = false;
    					}
    					if (!go) // 경사로를 놓을 수 없는경우
    						return false; // 종료
    					else{ // 경사로를 놓을 수 있는 경우 
                             //cnt를 0으로 초기화하고
    						cnt = 0; 
                            // i의 index를 옮긴다는 변수를 true로
    						jmp = true; 
    					}
    				}
    			}
    			else{
    				return false; // 높이차이가 1이상 나면 종료
    			}
    		}
    		tmp = arr[y][i]; // 비교 대상 갱신
    		if (jmp) // i의 index를 옮겨야 하면
    			i += L - 1; // 내리막길에서 연속된 경사로 탐색 이후로 index 수정
    		jmp = false;// 다시초기화
    	}
    	return true;
    }
    
    int main(){
    	//freopen("14890.txt", "r", stdin);
    	cin >> N >> L;
    	for (int i = 0; i < N; i++){
    		for (int j = 0; j < N; j++){
    			cin >> map[i][j];
    			map2[j][i] = map[i][j];
    		}
    	}
    
    	int ans = 0;
    	for (int i = 0; i < N; i++){
    		if (ga_search(i, map))
    			ans++;
    	}
    
    	for (int i = 0; i < N; i++){
    		if (ga_search(i, map2))
    			ans++;
    	}
    	cout << ans << endl;
    
    
    	return 0;
    }

     

     

     

    # 이번 문제에서 숙지하면 좋을점

    1. abs 함수를 이용하자 => 절대값을 return해줌 => a=1, b=2 일때 abs(a-b) -> 1을 return

     

    2. 2차원 배열에서 가로 먼저 계산 후, 세로값을 증가시키는 로직이 필요하다면 굳이 함수의 매개변수로 X,Y를 다주지말자.

        bool ga_search(int y){
          int tmp = arr[y][0];
    
          for (int i = 1; i < N; i++){
              if (arr[y][i] == tmp)
              ....
           }
        }
        
        
        
        int main(){
            for (int i = 0; i < N; i++){
        	   ga_search(i)
            }
        }
    

    이렇게 나누어서 진행하는게 가독성도 좋고 실수도 줄여준다.

     

    3. 예제는 직접 손으로 작업하면서 분석 및 설계가 필요하다 => 히든케이스를 찾게되는 경우도 있음

     

    4. 무엇보다 문제보고 쫄지말자........

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    14503.로봇청소기  (0) 2020.06.01
    16236.아기상어  (1) 2020.05.31
    14890.경사로  (0) 2020.05.28
    1697.숨바꼭질  (0) 2020.05.27
    2468.안전영역  (0) 2020.05.26
    1012.유기농 배추  (0) 2020.05.26

    댓글 0

Designed by Tistory.