백준 15684 사다리 조작

좀 신박한 문제같아서 골랐다.

처음엔 이 섞는거 조건을 찾아야 하나... 하며 조건을 일일히 찾아보려 했다. 하지만 그렇게 푸는게 아니었다.

고민을 해보다가 좀 검색해봤다... 예상보다 간단했다. 가로 선을 그을 수 있는 경우의 수 공간을 탐색하는 방향으로 문제를 풀면 되었다.

DFS를 사용해서, 가로선을 긋는 경우의 수 공간을 탐색한다. 만약 가로선이 4개 이상 그어진 상태면 종료한다. -> 3개 초과일 경우 -1을 출력하므로

각 상태에서 game_check()을 통해 모든 세로선이 자기 자신으로 돌아오는지 확인한다. -> 돌아오는것을 확인하면, 그 값을 answer와 비교해 최소값으로 갱신한다.

 

로직을 글로 써보니 되게 간단한데, 처음 아이디어 떠오르기가 너무 어려운것 같다.

---

#include <iostream>
#include <vector>
#include <climits>

// int map[11][30];
bool visit[11][30]; // visit[세로선 x][가로선 y] x가 x+1과 y에서 연결됨.
int n, m, h; // 세로선 n 가로선 h 이미 있는 가로선 m
int answer;

// 각 세로선에서 내려가면서 자신으로 다시 돌아오는지 확인
bool game_check() 
{
    for (int i = 1; i <= n; i++)
    {  
        int cur_h = i;
        for (int j = 1 ; j <= h; j++)
        {
            if (visit[cur_h][j])
                cur_h = cur_h + 1;
            else if (visit[cur_h - 1][j])
                cur_h = cur_h - 1;
        }
        if (cur_h != i)
            return false;
    }
    return true;
}

// 연결 할 수 있는 가로선들을 골라 탐색
void dfs(int index, int count)
{
    if (count > 3) //3개 초과일 경우 -1 처리
        return;
    
    if (game_check()) // 종료상태인지 확인
    {
        answer = std::min(answer, count); // 최소값 갱신
        return;
    }

    for (int i = index; i <= h; i++) // 가로선 경우의 수는 맨 윗줄부터
    {
        for (int j = 1; j <= n; j++) // 세로선들을 순회하며
        {
            if (visit[j][i]) // 이미 가로선 그어져있는지
                continue;
            if (visit[j-1][i]) // 앞에 가로선이 그어져있는지
                continue;
            if (visit[j+1][i]) // 뒤에 가로선이 그어져있는지
                continue;
            
            visit[j][i] = true; // 현재 위치에 가로선을 긋고
            dfs(i, count+1); // 다음 탐색 
            visit[j][i] = false; // 원래상태로 복귀
        }
    }
}

int main()
{
    
    std::cin >> n >> m >> h;
    answer = INT_MAX;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        std::cin >> a >> b;
        visit[b][a] = true;
    }

    dfs(1, 0);
    if (answer == INT_MAX)
        answer = -1;
    std::cout << answer;

}

 

좀 어려운것을 잡아보고 있는데 확실히 솔루션 떠올리는게 어렵다... 계속해서 더 풀어봐야겠다.

 

오늘도 평온한 하루가 되길. 슨민.