[백준OJ] 15684번 사다리 조작

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

15684번: 사다리 조작

---

 

 

풀이

maze[i][j]=k 라고 한다면, j번 가로선에서, i와i+1사이에 선이 있다면 k=1, 없다면 k=0으로 설정을 해준다.

백트래킹을 이용해서 가로선이 놓여있지 않은곳에 최대 3개의 가로선을 놔두면서, 각 경우마다 i번째 세로선의 결과가 i가 나오는지 체크를 해주며 최솟값을 갱신해주면된다.

 

이때 가로선이 없다는 의미는 b와 b+1사이에 가로선이 없어야 함과 동시에, b-1과b사이에 가로선또한 없어야 하므로 조건에 추가해주는것을 유의해야한다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int maze[11][31]={0};
int n,m,h;
int result=4;


//i번 세로선의 결과가 i번인지 확인
bool check(){
    for(int i=1;i<=n;i++){
        int now=i;
        int goal=i;
        
        for(int j=1;j<=h;j++){
            if(maze[now][j]==1){
                now++;
            }
            else if(maze[now-1][j]==1){
                now--;
            }
        }
        
        if(now!=goal){
            return false;
        }
    }
    return true;
}

void dfs(int line,int cnt){
    //3개이상이면 어차피 불가능과 같은 출력이므로 return
    if(cnt>3){
        return;
    }
    //결과가 맞으면 result갱신
    if(check()){
        result=min(result,cnt);
    }
    
	
    for(int j=line;j<=h;j++){
        for(int i=1;i<n;i++){
        	//해당 가로선이 없으면 백트래킹
            if(maze[i][j]==0&&maze[i-1][j]==0){
                maze[i][j]=1;
                dfs(j,cnt+1);
                maze[i][j]=0;
            }
        }
    }
}

int main() {
    cin>>n>>m>>h;
    
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        maze[b][a]=1;//a번 가로선에 b와b+1사이에 가로선이 있다.
    }
    dfs(1,0);
    cout<<(result==4?-1:result);
  
	return 0;
}