Gidhub BE Developer

[BOJ] 14890. 경사로

2018-10-18
goodGid
Algorithm

Problem

Problem URL : 경사로

[1] Answer Code (18. 10. 18)

#include<iostream>
#include<vector>
#include<cstring>
#define p pair<int,int>
using namespace std;

int dx[] = {0,1};
int dy[] = {1,0};

int map[100][100];
int v[100][100];

int n,l;
int ans;
int dir; // 0 is Row Direction, 1 is Column Direction

bool inRange(int x, int y){
    if( x < 0 || x >= n || y < 0 || y >= n)
        return false;
    return true;
}

void dfs(int x, int y, int pre_value){
    if( x == n || y == n ){
        ans++;
        return ;
    }
    
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if(map[x][y] == pre_value){ // ex) 2 2 형태
        dfs(nx,ny,map[x][y]);
    }
    else if( map[x][y] == pre_value + 1){ // ex) 2 3 형태
        int pivot_value = map[x][y];
        for(int i=0; i<l; i++){
            x -= dx[dir];
            y -= dy[dir];
            
            /*
             1. l=2 , [2 3] 이렇게 주어졌을 때 왼쪽으로 범위를 벗어나는 경우
             2. 설치해야하는 위치에 이미 경사로가 설치된 경우
             3. 경사로를 놓는 과정에 pivot 값과 다를 경우
             */
            if(! inRange(x,y) || v[x][y] == 1 || map[x][y] + 1 != pivot_value)
                return ;
            v[x][y] = 1;
        }
        dfs(nx,ny,pre_value + 1);
        
    }
    else if( map[x][y] == pre_value - 1){ // ex) 3 2 형태
        int pivot_value = pre_value;
        for(int i=0; i<l; i++){
            /*
            [2]
             1. l=2 , [3 2] 이렇게 주어졌을 때 왼쪽으로 범위를 벗어나는 경우
             2. 설치해야하는 위치에 이미 경사로가 설치된 경우
             3. 경사로를 놓는 과정에 pivot 값과 다를 경우
             */
            if(! inRange(x,y) || v[x][y] == 1 || map[x][y] + 1 != pivot_value)
                return ;
            v[x][y] = 1;
            x += dx[dir];
            y += dy[dir];
        }
        dfs(x,y,pre_value - 1);
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> l;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> map[i][j];
    
    // Row
    dir = 0;
    for(int i=0; i<n; i++){
        memset(v,0,sizeof(v));
        dfs(i,0,map[i][0]);
    }
    
    // Column
    dir = 1;
    for(int i=0; i<n; i++){
        memset(v,0,sizeof(v));
        dfs(0,i,map[0][i]);
    }
    
    cout << ans << endl;
    
    return 0;
}

Review

  • 삼성 역량 테스트 기출 문제

  • 문제를 잘못 해석하는 실수를 범했다.

  • 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.

  • 낮은 곳에 경사로를 설치해야하는 건데 높은곳에서도 설치가 가능하다고 생각했다.

  • [2]에서 주의할 점이 있다.

  • 코드의 순서에 따라 답이 틀리는 경우가 발생한다.

  • 만약 아래처럼 코드 순서를 배치한다면 틀리게 된다.

for(int i=0; i<l; i++){
    v[x][y] = 1;
    x += dx[dir];
    y += dy[dir];
    /*
        1. l=2 , [3 2] 이렇게 주어졌을 때 왼쪽으로 범위를 벗어나는 경우
        2. 설치해야하는 위치에 이미 경사로가 설치된 경우
        3. 경사로를 놓는 과정에 pivot 값과 다를 경우
        */
    if(! inRange(x,y) || v[x][y] == 1 || map[x][y] + 1 != pivot_value)
        return ;
}
dfs(x,y,pre_value - 1);

  • 범위를 체크하는 inRange(x,y) 코드 때문이다.

  • 다음과 같은 예를 들 수 있다.

Index : [1 2 3] 순서
Value : [3 2 2] 값
경사로 크기 : 2

현재 (1,1)이라고 가정

가리키는 Index : 2
pivot_value : 3
변화된 x = 1
변화된 y = 3

가리키는 Index : 3
pivot_value : 3
변화된 x = 1
변화된 y = 4

이 후 for을 나와
dfs(x,y,pre_value - 1)를 호출 후 

if( x == n || y == n ){
    ans++;
    return ;
}
위 코드가 돌아가야하는데 


x += dx[dir];
y += dy[dir];
if(! inRange(x,y) || v[x][y] == 1 || map[x][y] + 1 != pivot_value)
    return ;

위 코드 순서로 진행된다면
재귀 호출을 못하게 되며(= ans++ 작업이 이뤄지지 않는다.)
결과값이 틀리게 된다.

Recommend

Index