[C/C++] BOJ 15684 :: 사다리 조작

BOJ 15684 :: 사다리 조작

문제 링크 : https://www.acmicpc.net/problem/15684

나의 풀이

1) 사다리 배열에 선을 표시한다. (1열에 그려질 경우, 1열에서 2열로 가는 위치에 선이 있는 것이다.)

2) 현재 위치, 왼쪽, 오른쪽에 선이 그려져 있지 않은 경우, 선을 그려 나간다.

3) 주어진 개수만큼 선을 그렸을 때, 올바른 위치에 도착하는지 확인한다.

기준 번호 i 에서 시작하였을 때, i 열이 표시된 경우, 오른쪽으로 이동한다.

       i -1열이 표시된 경우, 왼쪽으로 이동한다.

현재의 사다리 라인의 번호를 갱신한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_15684/BOJ_15684.cpp

#include<iostream>
#include<vector>
using namespace std;
 
struct node
{
    int x;
    int y;
};
 
int N, M, H, a, b;
int ans = -1;
bool flag; // 출발지와 도착지가 같은지 확인하는 변수
bool ladder[32][12]; // 사다리판
vector<node> v; // line을 그릴 수 있는 위치를 저장해놓은 벡터
 
// 출발지와 도착지가 같은지 확인하는 함수
bool operate()
{
    for (int node = 1; node <= N; node++)
    {
        int line = node;
        int row = 1;
 
        while (row <= H)
        {
            // 오른쪽으로 이동
            if (ladder[row][line]) line += 1;
            // 왼쪽으로 이동
            else if (ladder[row][line - 1]) line -= 1;
            row++;
        }
        // 출발지와 도착지가 다르면 false
        if (node != line) return false;
    }
    // 모든 node를 탐색했을 때, 출발지와 도착지가 같으면 true
    return true;
}
 
// line을 그리는 함수
// _count : 현재 line 그린 개수,
// _num : line 그릴 목표 개수,
// ord : 그릴 수 있는 line 위치가 담긴 vector의 시작 index
void addline(int _count, int _num, int ord)
{
    // 목표한 개수만큼 line을 그렸으면 올바른 도착지에 갔는지 확인하여 ans 갱신
    if (_count == _num)
    {
        flag = operate();
        if (flag) ans = _num;
        return;
    }
 
    // line 그리기
    for (size_t i = ord; i < v.size(); i++)
    {
        int _x = v[i].x;
        int _y = v[i].y;
 
        // 현재 위치에 line이 그려져 있거나 양쪽에 line이 그려져 있으면 continue
        if (ladder[_x][_y] || ladder[_x][_y-1] || ladder[_x][_y+1]) continue;
        ladder[_x][_y] = true;
        addline(_count + 1, _num, i+1);
        ladder[_x][_y] = false;
 
        if (flag) return;
    }
}
 
int main(void)
{
    cin >> N >> M >> H;
 
    for (int i = 0; i < M; i++)
    {
        cin >> a >> b;
        ladder[a][b] = true;
    }
 
    node nd;
 
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j < N; j++)
        {
            if (!ladder[i][j])
            {
                nd.x = i;
                nd.y = j;
                v.push_back(nd);
            }
        }
    }
 
    // line  0개 그리기, 1개 그리기, 2개 그리기, 3개 그리기
    // 이미 ans가 갱신되었으면 최솟값이 결정된 것이니 끝낸다.
    for (int i = 0; i <= 3; i++)
    {
        if(!flag) addline(0, i, 0);
    }
 
    cout << ans;
 
    return 0;
}