[ 백준 15684 ] 사다리 조작 (C++)

백준의 사다리조작(15684) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 사다리 게임을 하는데, 기존에 세팅 되어 있는 사다리 게임에서 가로선을 추가해서 1번은 1번, 2번은 2번에 올 수 있도록

  사다리 게임을 조작해야 하는 문제이다.

- 입력으로 가로선을 놓을 수 있는 위치의 갯수가 주어진다.

- 모든 위치에 가로선을 다 놓아보면서, 가로선의 갯수가 최소가 될 때, 그 최소값을 출력하면 되는 문제이다.

[ 문제풀이 ]

1. 놓을 수 있는 모든 가로선에 다 놓아보면서 최소값을 갱신해 나가야 하는 완전탐색 문제이다.

2. 먼저 입력으로, 이미 연결되어 있는 가로선들의 정보가 주어진다.

   2개의 정수로 입력이 되며, (a, b)의 의미는 b와 b+1번 세로선이 a번 가로선에 의해서 연결되어 있습니다. 라는 의미이다.

   나는 이부분을 표시해 놓기 위해서 이미 방문했다는 의미의 Visit 2차원 배열을 사용했으며,

   Visit[b][a] = true로 표시해 주었다.

3. 이후에, 조합을 구하는 식으로 문제를 풀어나갔다. 놓을 수 있는 가로선의 위치 1번에서부터 H번까지 반복하면서

   세로선이 연결되어 있지 않은 부분이라면, 연결을 시켜보았다.

   코드에서 구현한 함수는 (Select_Line(int Idx, int Cnt)) 함수안에 내용이 구현되어 있다.

   조합을 구현할 때, 주의해야 할 점은 가로선끼리는 서로 연결될 수 없다는 점에만 조심을 하면 된다.

   위에서 입력을 받을 때, Visit[b][a] = true로 설정을 해 놨다. 이 말을 풀어서 말해보자면 b와 b+1번 세로선이 a번

   가로선에 의해 연결되어 있음을 의미하고, 이 말은 한 단계 더 생각을 해보면, b+1번과 b+2번은 a번 가로선에 의해

   연결될 수 없습니다 가 된다. 한번 더 생각해보면, b-1번과 b번은 a번 가로선에 의해 연결될 수 없습니다.

   라는 의미를 가지고 있다. 가로선끼리 연결될 수 없기 때문에 조합을 선택할 때, 이 3가지 경우에 대해 모두 고려를 해 주어야한

   다.

4. 조합을 하나 하나 만들 때마다, 사다리게임을 진행해봐야 한다. 진행해보면서 만약 게임이 조작이 되었다면, 추가한 가로선의

   갯수를 최소값으로 갱신해주어야 하며, 문제의 조건인 추가된 가로선의 갯수가 3개가 넘는다면 -1을 출력하라고 했으므로

   추가해야할 가로선의 갯수가 3개가 넘는다면 그대로 함수를 종료하는 식으로 구현을 해 주었다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int N, M, H, Answer;
int MAP[11][30];
bool Visit[11][30];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    Answer = 9999999;
    cin >> N >> M >> H;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        Visit[b][a] = true;
    }
}
 
bool Ladder_Game()
{
    for (int i = 1; i <= N; i++)
    {
        int Current_Num = i;
        for (int j = 1; j <= H; j++)
        {
            if (Visit[Current_Num][j] == true) Current_Num = Current_Num + 1;
            else if (Visit[Current_Num-1][j] == true) Current_Num = Current_Num - 1;
        }
 
        if (Current_Num != i) return false;
    }
    return true;
}
 
void Select_Line(int Idx, int Cnt)
{
    if (Cnt >= 4) return;
    
    if (Ladder_Game() == true)
    {
        Answer = Min(Answer, Cnt);
        return;
    }
 
    for (int i = Idx; i <= H; i++)
    {
        for (int j = 1; j < N; j++)
        {
            if (Visit[j][i] == true) continue;
            if (Visit[j - 1][i] == true) continue;
            if (Visit[j + 1][i] == true) continue;
            
            Visit[j][i] = true;
            Select_Line(i, Cnt + 1);
            Visit[j][i] = false;
        }
    }
}
                            
void Solution()
{
    Select_Line(1, 0);    
 
    if (Answer == 9999999) Answer = -1;
    
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}