[알고리즘] 백준 15684 c++

문제 링크

15684번: 사다리 조작

틀린이유

• dfs 사용할 땐 시간초과 항상 고려해야함
• 시간 최대한 줄일 수 있는 방법 생각해야 함

문제 분석

문제

• 사다리 타기
• i번 세로선의 결과가 i번이 나와야 한다
• 그렇게 하기 위해 추가해야하는 가로선의 개수의 최솟값은?

입력

• 세로선 : 2 ≤ N ≤ 10
• 가로선 : 1 ≤ H ≤ 30
• 세로선 놓을 수 있는 위치 : 0 ≤ M ≤ (N-1)*H
• 가로선 정보 a, b : 1 ≤ a ≤ H, 1 ≤ b ≤ N-1

출력

• 추가해야하는 가로선 개수의 최솟값
• 단, 3보다 크거나 불가능할 경우 -1 출력

해결방안

1. 사다리 표현

   배열로 : board[35][15]

   가로선 연결여부 int로 (0: 연결 X, 1: 연결:O, 2: 새롭게 연결)

2. 가로선의 유무 확인 : check()

   if (board[i][j]) j++; // 오른쪽 이동
   else if (board[i][j - 1] != 0) j--; // 왼쪽 이동
   //else 아래로(열 그대로) 이동

3. 가로선 두는 방법 : dfs

---

1. 4% 시간초과

   dfs로 사다리의 개수 0~3까지 살펴보는게 중복이므로 Level의 개수로 나눠서 돌리는 게 아닌 dfs 내에서 모든 level에서 check

   • 잘못된 코드

   void dfs(int L){
   	if (L == cnt) {
   		check();
   		return;
   	}
   	...
   }
   
   int main(){
   	...
   	for (int i=0; i<=3; i++){
   		cnt = i;
   		dfs(0);
   	}
   	...
   }

   • 옳은 코드

   void dfs(int L){
   	check();
   	
   	if (L == 3) return;
   	...	
   }
   
   int main(){
   	...
   	dfs(0);
   	...
   }

2. dfs에서 사다리위치 선택할 때 앞에는 고려 안해도 됐음(이미 앞쪽에서 확인하므로 중복)
   -> 시작 위치 가지고 다니게 하여 시간 초과 문제 해결

   • 잘못된 코드

     void dfs(int L){
     	...
     	for (auto coord: coords) {
     		if (board[coord.X][coord.Y]) continue;
         board[coord.X][coord.Y] = 2;
         dfs(L + 1);
         board[coord.X][coord.Y] = 0;
     	}
     	...
     }

   • 옳은 코드

     void dfs(int L, int vi){
     	...
     	for (int i = vi; i<= coords.size(); i++) {
     		auto coord = coords[i];
     		if (board[coord.X][coord.Y]) continue;
         board[coord.X][coord.Y] = 2;
         dfs(L + 1, i+1);
         board[coord.X][coord.Y] = 0;
     	}
     	...
     }

3. 12% 틀렸습니다
   level을 0부터 시작하여 3까지 dfs는 깊이 탐색으로 쭉 들어가므로 답이 나왔다고 해서 그것이 최적(최솟값)이 아닐 수 있음
   → min 함수를 사용하여 최솟값을 가질 수 있게 해야함
   - 옳은 코드

        
        int ans = 0x7f7f7f7f; // Int의 근사 최댓값
        
        void dfs(int L, int vi){
        	...
        	if (ans < L) return;
        	if (check()) {
        		ans = min(ans, L);
        		return;
        	}
        	...
        }

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define X first
#define Y second
#define MAX 0x7f7f7f7f

int N, M, H;
int board[35][15];
vector<pair<int, int> > coords;
int ans = MAX;

bool isComplete;

bool check()
{
    for (int n = 1; n <= N; n++)
    {
        int j = n;
        for (int i = 1; i <= H; i++)
        {
            if (board[i][j] != 0)
                j++;
            else if (board[i][j - 1] != 0)
                j--;
        }
        if (j != n)
            return false;
    }

    return true;
}

void dfs(int L, int vi)
{
    if (ans < L) return;

    if (check())
    {
        ans = min(ans, L);
        return;
    }

    if (L == 3) return;

    for (int i = vi; i<coords.size(); i++){
        auto coord = coords[i];
        if (board[coord.X][coord.Y]) continue;
        board[coord.X][coord.Y] = 2;
        dfs(L + 1, i);
        board[coord.X][coord.Y] = 0;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> H;
    while (M--)
    {
        int a, b;
        cin >> a >> b;
        board[a][b] = 1;
    }

    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j < N; j++)
        {
            if (board[i][j] || board[i][j - 1] || board[i][j + 1])
                continue;
            coords.push_back(make_pair(i, j));
        }
    }

    dfs(0, 0);

    if (ans > 3) cout << "-1";
    else cout <<  ans;

    return 0;
}