백준 15684번 - 사다리조작

https://www.acmicpc.net/problem/15684

완전 탐색 문제로 DFS를 통해 선을 그으면서

i번의 세로선의 결과가 i번이 나오는지를 확인했다.

이런 문제는 세로선과 가로선의 기준을 잘 정해야 하는데

2차원 배열 ladder가 있을 때, ladder[세로선][가로선]으로 변수를 지정했다.

ladder[b][a]=1일 경우

b와 b+1의 세로선 사이에 a번째 가로선 행에 사다리가 있음을 의미한다.

먼저 문제를 해결하기 위해 접근한 방향은 다음과 같다.

1) 가로선을 몇개를 추가할지를 정한다(1~3개)

2) DFS를 통해 현재의 y번째 세로선에서 오른쪽 방향으로 가로선을 추가할 수 있으면 추가한다.

3) 만약 추가한 가로선의 개수가 1번에서 지정한 가로선의 개수와 같다면, i번의 세로선의 결과가 i번인지 확인한다.

4) i번의 세로선의 결과가 i번이 아니라면 2),3)번을 반복 실행한다. (모든 결과가 i번이라면 바로 종료)

5) 1번에서 추가할 가로선의 개수를 1개 증가 시켜준뒤 위의 작업을 반복한다.

기준을 어떻게 정하느냐에 따라, 다양한 방법으로 문제를 해결할 수 있다.

가로선을 이어줄 때, 왼쪽 방향과 오른쪽 방향을 모두 고려하는 방법도 생각했지만

예외 처리가 너무 많아지면서, 기준을 오른쪽으로만 생각해서 가로선을 이어주도록 했다.

#include <iostream>
#include <string.h>
using namespace std;
 
int ans=-1;
int N,M,H;
int ladder[12][32]={0};
int line_cnt=0; //추가할 가로선의 개수
 
int line_check(int y,int x){
    
    for(int j=x;j<=H;j++){
        if(ladder[y][j])    return line_check(y+1,j+1);
        if(ladder[y-1][j])  return line_check(y-1,j+1);
    }
    
    return y;
}
 
//i번째의 세로선의 결과가 i번인지 확인
bool solve(){
    
    for(int y=1;y<=N;y++){
        if(line_check(y,1)!=y){
            return false;
        }
    }
    return true;
}
 
void dfs_connect(int y,int cnt){
    
    if(cnt>3 || ans!=-1)
        return;
    
    if (line_cnt==cnt) {
        if (solve()) {
            ans = cnt;
        }
        return;
    }
    
    for(;y<N;y++){
        for(int x=1;x<=H;x++){
            //오른쪽 긋기
            if(ladder[y][x]==0){
                if(y==N-1 || (ladder[y+1][x]==0 && ladder[y-1][x]==0)){
                    ladder[y][x]++;
                    dfs_connect(y,cnt+1);
                    ladder[y][x]--;
                }
            }
        }
        
    }
    
}
 
int main(){
    
    cin>>N>>M>>H;
    
    if(M==0){
        cout<<0<<endl;
        return 0;
    }
    
    int a,b;
    for(int i=0;i<M;i++){
        scanf("%d %d",&a,&b);
        ladder[b][a]=1; //b,b+1세로선과 a가로선
    }
    
    for (int i = 0; i < 4; i++) {
        line_cnt = i;
        dfs_connect(1,0);
        
        if (ans != -1)
            break;
    }
    cout<<ans<<endl;
    
    return 0;
}