백준 15684번 사다리 조작 - C++ 풀이

---

 

1. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면 i와 (i+1)의 위치가 바뀐다.
2. 백트래킹으로 최대 3개의 가로선을 놓는 경우를 모두 시도해본다.

 

1. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면 i와 (i+1)의 위치가 바뀐다.

 i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면, 원래 결과 (i, i+1)에서 (i+1, i)로 결과가 바뀐다. 두 세로줄의 위치를 스왑한 것과 같은 효과를 얻게 된다. 이 사실을 이용하여 그어진 가로줄의 목록을 가지고 사다리 게임의 결과를 계산할 수 있다. (아래 코드에서 check() 함수 구현을 참고)

 

2. 백트래킹으로 최대 3개의 가로선을 놓는 경우를 모두 시도해본다.

 백트래킹을 이용하여 최대 3개의 가로선을 긋는 경우를 모두 시도해본다. 가로선이 연속되면 안된다는 사실과 가지치기에 유의한다. 가지치기를 해주지 않으니 시간 초과가 났다.

 

반응형

---

#include <iostream>
#include <vector>

using namespace std;

int N, M, H;
int minCnt = 4;
bool edge[31][11];

bool check() {
    for (int i=1; i<=N; i++) {
        int pos = i;
        
        for (int j=1; j<=H; j++) {
            if (edge[j][pos]) pos++;
            else if (edge[j][pos-1]) pos--;
        }
        
        if (pos != i) return false;
    }
    
    return true;
}

void DFS(int h, int cnt) {
    if (cnt >= minCnt) return;
    if (check()) minCnt = cnt;
    
    for (int i=h; i<=H; i++) {
        for (int j=1; j<N; j++) {
            if (edge[i][j] || edge[i][j-1] || edge[i][j+1]) continue;
            
            edge[i][j] = true;
            DFS(i, cnt+1);
            edge[i][j] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M >> H;
    
    for (int i=0; i<M; i++) {
        int a, b; cin >> a >> b;
        edge[a][b] = true;
    }
    
    DFS(1, 0);
    
    if (minCnt > 3) cout << -1;
    else cout << minCnt;

    return 0;
}