14890.경사로

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

14890번: 경사로

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

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

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

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

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

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

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

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. 무엇보다 문제보고 쫄지말자........