[삼성SW테스트] 백준 15684번 - 사다리 조작

2018년 상반기 삼성SW테스트 기출 문제다.

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

15684번: 사다리 조작

기존에 4방위 또는 8방위에 대해 이리저리 이동하는 문제 (로봇)를 BFS 또는 DFS로 이동하는 문제를 익숙하게 풀었다면 이 유형의 문제는 다리를 놓는 경우에 대한 완전 탐색을 요구하는 문제였다.

 

전자의 문제들은 2D bool 행렬에서 소규모 경로들을 조건에 맞게 하나하나 찾아 문제해결을 하는 반면(예: 삼성 SW테스트 기출문제 '인구이동' https://www.acmicpc.net/problem/16234), 이 유형의 문제는 0개, 1개, 2개, 3개만큼 다리를 놓는 모든 경우를 케이스별로 탐색하여 문제조건을 확인하는 문제다.

 

이 문제를 처음에 단순 브루트포스로 algorithm의 next_permutation함수를 통해 비트마스킹으로 풀까 생각하여 접근법이 꼬였지만,, 이런 유형이 나오면 앞으로는 바로 dfs 백트래킹으로 풀어야겠다. 완전탐색, 그중에서도 DFS또는 BFS가 각각 어떤 경우에 대해 더 효율적이겠다라는 느낌이 점점 잡혀와 좋다.

 

아래는 전체 C++ 소스코드. (1.096s / 2s)

 

#include <iostream>
#define max_N 11
#define max_H 31
using namespace std;
int N, M, H, a, b;
bool flag = false;
int cur_target;
bool line_[max_H][max_N - 1];
void falsing(){
    for (int i = 0; i < max_H; i++)
        for (int j = 0; j < max_N - 1; j++)
            line_[i][j] = false;
}
 
void backtracking(int curcount){
    // 1. 찾으면 종료
    if (flag)
        return;
    // 2. 기저사례 (정답을 확인하는 조건 도달)
    if (curcount == cur_target){
        bool possible = true;
        for (int col = 1; col <= N; col++){
            int col_tmp = col;
            for (int row = 1; row <= H; row++){
                // 오른쪽
                if (line_[row][col_tmp]){
                    col_tmp++;
                }
                // 왼쪽
                else if (col_tmp > 1 && line_[row][col_tmp - 1]){
                    col_tmp--;
                }
            }
            if (col_tmp != col){
                possible = false;
                break;
            }
        }
        if (possible){
            flag = true;
        }
        return;
    }
    // 3. 기저사례 이전의 경우에 대해 탐색 진행 코드
    for (int col = 1; col <= N-1; col++){
        for (int row = 1; row <= H; row++){
            if (!line_[row][col]){
                line_[row][col] = true;
                backtracking(curcount + 1);
                line_[row][col] = false;
            }
        }
    }
 
    // 4. 가장 바깥의 시행에 대한 함수 종료.
    return;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    falsing();
    cin >> N >> M >> H;
    for (int i = 0; i < M; i++){
        cin >> a >> b;
        line_[a][b] = true; // a행 b열 세로선과 a행 b+1열 세로선을 잇는 가로선 긋기.
    }
    for (int i = 0; i <= 3; i++){
        cur_target = i;
        backtracking(0);
        if (flag){
            cout << i << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
    return 0;
}