[백준]15684 사다리 조작 C++, python

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

15684번: 사다리 조작

시뮬레이션과 백트래킹으로 모든 조합을 만들면 된다.

i번째가 i번째로 가는 시뮬레이션 부분은 어렵지 않지만 백트래킹으로 조합을 만들때 중복되는 거 없이 수를 최소한으로 줄여야 통과할수 있었다.

 

#include<iostream>
#include<algorithm>
using namespace std;

int N, M, H;
int ladder[32][12];
int answer;

bool check() {
    int i, r, c;
    for (i = 1; i <= N; i++) {
        c = i;
        for (r = 1; r <= H; r++) {
            if (ladder[r][c] == 1) {
                c++;
            }
            else if (ladder[r][c - 1] == 1) {
                c--;
            }
        }
        if (c != i) {
            return false;
        }
    }
    return true;
}

void dfs(int ind, int x, int y) {
    if (answer <= ind) return;
    if (check()) {
        answer = ind;
        return;
    }
    if (ind == 3) return;

    for (int i = y; i <= H; i++) {
        for (int j = x; j <= N; j++) {
            if (ladder[i][j] == 0 && ladder[i][j - 1] == 0 && ladder[i][j + 1] == 0) {
                ladder[i][j] = 1;
                dfs(ind + 1, j, i);
                ladder[i][j] = 0;
            }
        }
        x = 1;
    }
}

int main() {
    cin >> N >> M >> H;
    int i, a, b;
    for (i = 0; i < M; i++) {
        cin >> a >> b;
        ladder[a][b] = 1;
    }
    answer = 4;
    dfs(0, 1, 1);
    if (answer == 4)
        cout << "-1";
    else
        cout << answer;
}

import sys; input = sys.stdin.readline
def check(v):
    # check start i to end i
    global N, H
    for i in range(1, N + 1):
        c = i
        for r in range(1, H+1):
            if v[r][c]:
                c += 1
            elif v[r][c - 1]:
                c -= 1
        if c != i:
            return False
    return True

def dfs(ind, x, y, v):
    global answer, N, M, H
    if answer <= ind:
        return
    if check(v):
        answer = min(answer, ind)
        return
    if ind == 3:
        return
    for i in range(y, H + 1):
        for j in range(x, N + 1):
            if v[i][j]: continue
            if v[i][j - 1] or v[i][j + 1]: continue
            v[i][j] = True
            dfs(ind + 1, j, i, v)
            v[i][j] = False
        x = 1

def main():
    global answer, N, M, H
    N, M, H = map(int, input().split())
    ladder = [[False for _ in range(N + 2)] for _ in range(H + 2)]
    for _ in range(M):
        a, b = map(int, input().split())
        ladder[a][b] = True
    answer = 4
    dfs(0, 1, 1, ladder)
    print(-1 if answer == 4 else answer)

if __name__ == "__main__":
    main()