15684번

15684번 -사다리 조작

이번 상반기에 대기업 알고리즘 문제로 나왔던 문제.

막상 가서 실전에서 문제를 풀 때에는 배열을 더 크게 잡아서 약간 미로탐색처럼 문제를 풀었었다. 

하지만 지금 다시 보면서 생각해보니, 각 점들을 노드라고 생각하여 방향 그래프를 완성하면 문제가 쉬워진다.

근데 이 문제에서 계속 헷갈렸던게 입력값이었다.. N,M,H 가 주어지는데 나는 평상시에 N을 세로, M을 가로로 놓고 문제를 많이 풀다보니 헷

갈려서 그냥 변수를 바꿔버렸다. X축은 X로 Y축은 Y로 바꿔서 문제를 풀었다.

그리고 좌표값들을 노드 번호로 바꿔서 문제를 풀었다. 즉 세로가 3, 가로가 4인 사다리로 보았을 때, (1,1)은 1번 노드로, (1,2)는 2번 노드로, 

(1,3)은 3번 노드로 이런식으로 좌표를 노드 번호로 바꾸어서 문제를 풀었다. x좌표,y좌표가 주어졌을 때 (x-1)*가로+y 를 이용하면 노드 번호

를 순서대로 구할 수 있게 된다.

그리고 맨 처음에 아래 방향으로 노드들을 모두 연결해준다. 아래에서 위로는 올라올 수 없기 때문에 위에서 아래방향으로 연결한다. 

이때 맨 마지막 줄을 한 줄 더 추가해서 맨 마지막 노드들도 아래 방향으로 가는 간선이 생기도록 만든다. 그래야 나중에 케이스를 구분할 때 

편하기 때문이다. 이렇게 만들면 모든 노드들은 아래 방향으로 이동할 수 있는 간선이 1개씩 생기고, 이 간선은 vector 의 0번 index에 들어가

게 된다. 그리고 간선을 입력받으면서 양방향으로 연결되도록 만들어준다. 이런식으로 하면 가로 방향 간선은 vector 의 1번 index에 들어간

다. 이렇게 주어진 연결을 모두 마치면 이제 for문을 이용해서 최대 3개까지 간선을 만드는 완전 탐색을 실행한다. (문제에서 4이상은 -1을 출

력하라고 했기 때문에..)

재귀함수를 이용해서 간선을 만들고 정답이 맞는지 find_last() 함수를 이용한다.

시작점에서 가로를 우선으로 움직이면서 방문한 곳은 visited 를 true 로 체크하면서 이동한다. 그러다가 맨 마지막 줄보다 아래로 내려가서 

더 이상 움직일 곳이 없을 때의 값을 시작값과 비교하면 되는데, 두 값을 빼고 가로 길이인 Y로 나누었을 때 나누어 떨어지면 맞는값이 된다.

처음에 시간초과가 발생했는데, go() 함수에서 before 라는 인자를 추가해서 중복되는 값을 없애서 시간내에 통과할 수 있게 되었다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
typedef struct pos
{
    int x;
    int y;
}pos;
 
int X, M, Y;
bool find_ans = false;
 
// 시작점으로부터 끝점을 찾는 함수
bool find_last(vector<vector<int>> &node, int start)
{
    bool visited[300] = { false, };
    int cur = start;
    while (true)
    {
        visited[cur] = true;
        int next;
        if (node[cur].size() == 2)
        {
            next = node[cur][1];
            if (!visited[next])
                cur = next;
            else
                cur = node[cur][0];
        }
        else if(node[cur].size()==1)
        {
            next = node[cur][0];
            cur = next;
        }
        else
        {
            break;
        }
    }
 
    if ((cur - start) % Y == 0)
        return true;
    else
        return false;
 
}
void go(vector<vector<int>> &node, int k,int before)
{
    if (find_ans)
        return;
 
    if (k == 0)
    {
        bool finish = true;
 
        //첫번째 노드들을 하나씩 탐색하며 내려감
        for (int i = 1; i <= Y; i++)
        {
            if (!find_last(node, i))
            {
                finish = false;
                break;
            }
        }
 
        if (finish)
            find_ans = true;
 
 
        return;
    }
 
    // 새로 만드는 간선(가로방향)
    for (int i = before+1; i <= X * Y; i++)
    {
        if (node[i].size() < 2 && i%Y != 0)
        {
            node[i].push_back(i + 1);
            node[i + 1].push_back(i);
            go(node, k - 1,i);
            node[i].pop_back();
            node[i + 1].pop_back();
 
        }
    }
 
 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
 
    cin >> Y >> M >> X;
 
    vector<vector<int>> node((X+1)*Y + 1);
 
    //세로 방향의 노드를 연결
    for (int i = 1; i <= Y * X; i++)
    {
        node[i].push_back(i + Y);
    }
 
    //가로 방향의 노드를 연결
    for (int i = 0; i < M; i++)
    {
        int a, b, to, from;
        cin >> a >> b;
        to = (a - 1)*Y + b;
        from = to + 1;
        node[to].push_back(from);
        node[from].push_back(to);
    }
 
    // 0번,1번,2번,3번 완전 탐색
    for (int i = 0; i < 4; i++)
    {
        go(node, i,-1);
 
        if (find_ans) {
            cout << i << endl;
            break;
        }
    }
 
    // 완전 탐색을 해도 정답을 찾을 수 없을 때
    if (!find_ans)
        cout << -1 << endl;
 
 
 
 
    return 0;
}