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

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

15684번: 사다리 조작

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, M, H, a, b;
int result = MAX;
int arr[31][11]; //H, N
int max_cnt;

bool check() //i번째 선이 i번째로 돌아오는가?
{
    for (int i = 1; i <= N; i++) //세로선
    { 
        int cur = i;
        for (int j = 1; j <= H; j++) //가로선
        { 
            if(arr[j][cur]) cur++; //우측이동
            else if(arr[j][cur - 1]) cur--; //좌측이동
        }
        if(cur != i) //돌아왔는가?
        { 
            return false;
        }
    }
    return true;;
}

void dfs(int y, int cnt)
{
	if(max_cnt == cnt) 
    {
		if(check()) 
        {
			result = min(result, cnt);
		}
		return;
	}

	for (int i = y; i <= H; i++)
    {
        for (int j = 1; j < N; j++)
        {
            if(arr[i][j-1] || arr[i][j] || arr[i][j+1]) continue; //사다리 설치 불가 조건
            arr[i][j] = 1; // 사다리 추가
            dfs(i, cnt + 1); // 사다리 갯수 카운트
            arr[i][j] = 0; // 추가한 사다리 삭제 (백트래킹)
        }
    }
    return;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> H; //세로선, 가로선, 위치

    while(M--)
    {
        cin >> a >> b; 
        arr[a][b] = 1; //가로선 표시
    }

    for (int i = 0; i <= 3; i++) //가로선 추가할때마다 확인 (최대 3개)
    { 
        max_cnt = i;
        dfs(0, 0);
    }

    cout << (result == MAX ? -1 : result);
    return 0;
}

백트래킹을 활용한 문제이다.

혼자 힘으로 풀기 어려워서 검색을 많이 참고했다.

 

i번째 선이 이동하여 다시 i번째 선으로 돌아오는지 체크하는 함수를 두고,

백트래킹을 통해서 사다리를 추가해보면서 위에 다시 돌아오는지 함수를 통해 체크해준다.

 

가로선은 최대 3개까지 추가가 가능하므로, 0개부터 3개까지의 가로선을 추가할때 마다 각 케이스에 대해서 위에 체크 함수와 백트래킹을 확인해준다.

 

dfs로 인자를 넘길때 사다리가 설치 가능한 현재 i 값을 넘겨줌으로써 이미 탐색한 그전까지의 값을 스킵해준다.

이를 통해 시간초과 방지가 가능하다.

 

아직 완벽히 이해가 된 것이 아니어서 다시 한번 살펴볼 필요가 있을 것 같다.