사다리 조작

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
using namespace std;
// 0511 ~ 0736
int N, M, H, ans=1e9;
pair<bool,bool> graph[35][35];
int cnt[35];
bool startGame()
{
    for(int i=1;i<=N;i++)
    {
        int loc = i;
        for(int j=1;j<=H;j++)
        {
            auto cur = graph[j][loc];
            /* 왼쪽으로 가는 경우 */
            if(cur.first){
                loc--;
            }else if(cur.second){
                /* 오른쪽으로 가는 경우 */
                loc++;
            }
            /* 그냥 아래로 가는 경우 - 방향 유지 */
        }
        if(loc != i) return false;
    }
    return true;
}
void DFS(int depth, int curH){
    if(depth == 4)
    {
        return;
    }
    for(int i=curH;i<=H;i++)
    {
        for(int j=1;j<=N;j++)
        {
            auto cur = graph[i][j];
            auto prev = graph[i][j-1];
            auto next = graph[i][j+1];
            /* 가로선이 있으면 놓을 수 없으므로 PASS */
            if(cur.first or cur.second) continue;
            /* 오른쪽에 가로선 놓기 */
            if(!cur.second and !next.second and !cur.first){
                graph[i][j].second = true;
                graph[i][j+1].first = true;
                if(startGame()) {
                    ans = min(ans,depth);
                    graph[i][j].second = false;
                    graph[i][j+1].first = false;
                    goto stop;
                }
                DFS(depth+1, i);
                graph[i][j].second = false;
                graph[i][j+1].first = false;
            }
        }
    }
    stop:;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    /* N=세로선, H=높이 */
    cin >> N >> M >> H;
    for(int i=0;i<M;i++)
    {
        int a,b;
        cin >> a >> b;
        graph[a][b].second = true; // 오른쪽 연결
        if(b+1 <=N)
            graph[a][b+1].first = true; // 왼쪽 연결
    }
    if(startGame())
    {
        cout << 0;
        return 0;
    }
    DFS(1,1);
    if(ans == 1e9) ans = -1;
    cout << ans;
    return 0;
}

• 로직
  • 최대 3-depth 백트래킹을 통해 사다리를 놓는 경우를 찾는다
  • starGame() --> 사다리게임을 하여 하나라도 자신이 아니면 바로 return false

• 오래걸린 이유
  • 해당 문제는 총 300개중 3개를 골라서 사다리를 놓는 경우의 수 (300C3)라서 450만개 정도가 나와서 충분히 시간안에 해결이 가능하다
  • 나는 모든 세로축 에서 왼쪽 / 오른쪽 모두 사다리를 놓는 경우를 검사함
    --> 한쪽만 하면 되는데 양쪽 모두 해서 중복이 많이 발생해서 시간초과가 났음