[ 백준 15684 ] 사다리 조작

안녕하세요 !!! 우디 ✨ 입니다 .

 

문제

백준 사다리조작 링크

 

문제 설명

우선, 코드의 구조를 대략적으로 아래처럼 구분했습니다.

• 완전 탐색 ( DFS 사용 )으로 모든 경우의 수를 가려내 답을 찾아냄 .
• 주어진 예제만으로 답을 찾아냄 .

 

문제를 읽자마자 완전 탐색을 해서 답을 가려내야 겠구나 ,,, 라는 생각이 먼저 들었습니다.

또한, 완전 탐색을 하기도 전에 주어진 예제가 답 ( 0 // 놓는 다리가 없으니 ) 인 경우를 살펴보았는데요 ~ !

• 주어진 예제속 가로선 = 0 일 때 // 놓을 수 있는 다리가 없으니 바로 답이 0
• 다리를 놓기도 전에 주어진 사다리가 정답 ! // 다리 놓을 것도 없이 퍼풱트한 사다리 ~

 

구현 ( 주석 설명 O )

​x
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
​
int num = 0;
void dfs(int arr[40][20], int hh, int f, int e);
int check(int arr[40][20]);
//배열(사다리 정보)을 매개변수로 넘겨주면 i번이 i번으로 나오는지 검사.
​
int arr[40][20];
int n, m, h;
​
int ans = -1;//정답 담을 변수
​
int main()
{
    cin >> n >> m >> h;
​
    for (int i = 0; i < h; i++)
        memset(arr[i], -1, sizeof(int) * n);//배열 -1로 초기화
​
    if (m == 0)
    {
        cout << 0 << endl;
        return 0;
    }//바로 정답(첫번째)
    else
    {
        int a, b;
        for (int i = 0; i < m; i++)
        {
            cin >> a >> b;
            arr[a - 1][b - 1] = b;
            arr[a - 1][b] = b - 1;
        }//사다리 정보 갱신
​
        if (check(arr) == 6)
        {
            cout << 0 << endl;
            return 0;
        }//바로 정답(두번째)
​
        for (int i = 1; i < 4; i++) {//완전탐색 깊이 3번까지만 ! 초과면 답 -1
            dfs(arr, i, 0, 0);
            if (ans!= -1) {
                cout << ans << endl;
                return 0;
            }
            num = 0;//새로운 dfs를 위해 초기화
        }
    }
    cout << -1 << endl;//완전 탐색 깊이 3초과 답 -1
}
​
​
void dfs(int arra[40][20], int hh, int f, int e)//hh는 가로선 갯수
{
    num++;
    if (num == hh)
    {
        for (int k = f; k < n; k++)
        {
            for (int o = e; o < h; o++)
            {
                if (k + 1 != n && arra[o][k] == -1 && arra[o][k + 1] == -1)//놓을 수 있는 경우
                {
                    arra[o][k] = k + 1;
                    arra[o][k + 1] = k;
                    if (check(arra) == 6)
                    {
                        ans = hh;
                        break;
                    }
                    arra[o][k] = -1;
                    arra[o][k + 1] = -1;//원상복구 ~
                }
            }
            e = 0;//k 라인의 처음부터 탐색할려고 !
        }
    }
    else
    {
        for (int k = f; k < n; k++)
        {
            for (int o = e; o < h; o++)
            {
                if (k + 1 != n && arra[o][k] == -1 && arra[o][k + 1] == -1)//놓을 수 있는 경우
                {
                    arra[o][k] = k + 1;
                    arra[o][k + 1] = k;
                    dfs(arra, hh, k, o);
                    // dfs 끝나고 돌아오면 깊이 갱신 and 사다리 갱신
                    num--;
                    arra[o][k] = -1;
                    arra[o][k + 1] = -1;
                }
            }
            e = 0;
        }
    }
}
int check(int arr[40][20])//i번이 i번 나오는지
{
    int a = 0;
    int b = 0;
    for (int i = 0; i < n; i++)
    {
        a = 0;
        b = i;
        while (a != h)
        {
            if (arr[a][b] != -1)
            {
                if (arr[a][b] > b) b = b + 1;//오른쪽 연결
                else b = b - 1;
            }
            a = a + 1;
        }
        if (i != b) {
            return 4;
        }//안맞게 나옴
    }
    return 6;//맞게 나왔음
}
​

 

어려운 점 및 개선점

가로선 , 세로선 , 가로선 놓을 수 있는 위치 갯수 이 차이점들을 이해 못하고 풀면서 이해할려고 했더니 시간이 따블 ~^^

구현은 어려운 점은 없었다 .(이번에도 dfs 끝날 때 갱신 자꾸 안해줘서 당황탔지만 ~^^)

 

근데,

4월에 하고 9월풀고 10월에 업로드 하는 거 실화냐 ,,,ㅋㅋㅋㅋㅋㅋㅋㅋㅋ맞자 ^^👊

앞으로 자주 자주 돌아오겠습니당 😝💛