[C] 사다리 조작

백준 15684번

 

출력조건을 제대로 안읽은 값을 치룬 문제...

답이 3 이상이면 그만 셌어야했는데 문제만 읽고 그 점을 생각 못했다ㅠㅠ

골드 4 수준인데 틀리고 시간초과 나서 속상했다..

 

아무튼 삼성 기출답게 그냥 다 구현했다

 

dfs로 사다리를 그려가면서 답이 되는지를 체크했다

답이 되는지 체크해주는 isEnd 함수에서는 1부터 N까지 i번째가 i번째로 내려가는지 확인했다

풀면서 중간에 실수 했던거는 dfs 함수 내부에서 아무 생각없이 다시 (1,1)위치부터 for문으로 확인했던것!

이미 확인했던 부분이니까 중복을 막으려면 중간부터 다시 반복문을 돌아주어야 한다

그래서 while문으로 고쳐서 해결!

 

#include <stdio.h>
 
int graph[35][15]; 
// graph[3][2] == 1 means there is a number 3 line between 3~4
 
int N,H;
int ans = 1000000;
 
void printGraph()
{
    for(int i = 1 ; i <= H ; i++){
        for(int j = 1 ; j < N ; j++) printf("%d ",graph[i][j]);
        printf("\n");
    }
    printf("\n");
}
bool isEnd(){
    for(int i = 1; i <= N ; i++){
        int now = i, depth = 1;
        //printGraph();
        while(depth<=H){
            while(!graph[depth][now]&&!graph[depth][now-1]) {
                depth++;
            }
            if(depth>H) break;
            if(graph[depth][now]==1) now++;
            else if(graph[depth][now-1]==1) now--;
            depth++;
        } 
        if(i!=now) return false;
    }
    return true;
}
 
void dfs(int cnt, int i, int j){
    if(cnt>3) return;
    if(isEnd()) {
        if(ans>cnt) ans = cnt;
    }
    while(i<=H){
        while(j<N){
            if(!graph[i][j]&&!graph[i][j-1]&&!graph[i][j+1]){
                graph[i][j]=1;
                dfs(cnt+1,i,j+1);
                graph[i][j]=0;
            }
            j++;
        }
        i++;
        j = 1;
    }
}
 
int main(){
    int M;
    scanf("%d %d %d",&N,&M,&H);
    while(M--){
        int a,b;
        scanf("%d %d",&a,&b);
        graph[a][b] = 1;
    }
    dfs(0,1,1);
    if(ans==1000000 || ans > 3) printf("-1\n");
    else printf("%d\n",ans);
}