BOJ 15684 - 사다리 조작

www.acmicpc.net/problem/15684

15684번: 사다리 조작

처음에 dfs 로 처리하려고 했으나, 사다리가 끝에 도달 했을때, 끝나지 않고 다른 지점을 방문하는

오류를 계속 범하고 있어서 통과하지 못했다.

dfs 는 한쪽을 쭉 다 방문한 다음 다른 쪽을 방문하여 전체를 다 방문하는 것인데

문제풀때, dfs 에 대한 개념 자체를 모호하게 이해하고 있었던것 같다.

답을 못 찾다가 다른 분들의 풀이를 보고서 이해하게 되었다.

 

1. 전체 놓을 수 있는 가로선의 사다리 중 최대 3개만 뽑아서 처리한다 (조합)

2. 사다리를 내려갈때, 처음에 내려가기 시작한 열과 다른 번호로 매칭 된다면, 문제의 조건을 부합하지 못하는 것이므로, false 를 반환시키게 하고 그렇지 않다면 true 를 반환하게 한다

3. visited[b][a] = true 는 b 번째 세로선과 b + 1 번째 세로선을 a 번째 가로선과 연결 시켰다는 의미이며,

동시에 여러개의 가로선이 연결되어서는 안되므로, visited[b - 1][a] 가 true 이고 visited[b][a] 가 true 인 경우,

혹은 visited[b + 1][a] 가 true 이고 visited[b][a] 가 true 인 경우 오류로 처리해줘야한다.

 

 

- c++

 

#include <algorithm>
#include <iostream>
 
#define INF 1e9
 
using namespace std;
 
int n, m, h, answer = INF;
int adj[11][31];
bool visited[11][31];
 
bool is_valid() {
    for (int i = 1; i <= n; ++i) {
        int temp = i;
        for (int j = 1; j <= h; ++j) {
            if (visited[temp][j]) temp += 1;
            else if (visited[temp - 1][j]) temp -= 1;
        }
        if (temp != i) return false;
    }
    return true;
}
 
void recursion(int idx, int depth) {
    if (depth >= 4) return;
    
    if (is_valid()) {
        answer = min(answer, depth);
        return;
    }
    
    for (int i = idx; i <= h; ++i) {
        for (int j = 1; j < n; ++j) {
            if (visited[j][i]) continue;
            if (visited[j - 1][i]) continue;
            if (visited[j + 1][i]) continue;
            
            visited[j][i] = true;
            recursion(i, depth + 1);
            visited[j][i] = false;
        }
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> m >> h;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        visited[b][a] = true;
    }
    
    recursion(1, 0);
    
    if (answer == INF) answer = -1;
    cout << answer;
    
    return 0;
}