백준 15684번 사다리 조작

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

백준 15683번 감시(http://jaimemin.tistory.com/1070)와 유형이 비슷한 브루트 포스(Brute Force) 문제였습니다.

알고리즘은 아래와 같습니다.

1. 사다리를 표시할 때 ladder[y][x] = true라고 하면 y번째 높이에서 x ~ (x+1)을 이어주는 다리를 놓는다고 표시해줍니다.

2. 사다리를 0개부터 3개까지 설치해보고 설치할 때마다 DFS 함수를 호출해줍니다.

i)  현재 높이에서부터 (H-1)번째 높이까지 다리를 하나하나 설치해보며 DFS 함수를 재귀호출합니다.

ii) 기저 사례로 설치하고자 하는 사다리의 개수가 DFS 함수를 호출하면서 설치한 사다리의 개수가 같아지면 i번째 사다리가 i번째 지점에 도착하는지 확인합니다.

a) ii)가 참이라면 flag를 참으로 설정하고 현재 설치한 다리의 수를 출력해줍니다.

b) ii)가 거짓이라면 백트래킹해서 다른 다리들을 설치해봅니다.

3. 다리를 3개까지 설치했는데도 조건을 만족하지 못한다면 -1을 출력합니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 30;

 

int N, M, H;

int ladderCnt;

bool flag;

bool ladder[MAX][9 + 2];

 

void DFS(int y, int cnt)

{

        //답을 찾았으므로

        if (flag)

                 return;

        //기저 사례

        if (ladderCnt == cnt)

        {

                 bool possible = true;

                 for (int i = 1; i <= N; i++)

                 {

                         int row = i;

                         for (int j = 0; j < H; j++)

                                 //오른쪽

                                 if (ladder[j][row])

                                          row++;

                                 //왼쪽

                                 else if (row > 1 && ladder[j][row - 1])

                                          row--;

 

                         //i번 세로선의 결과가 i번이 나와야 한다

                         if (i != row)

                         {

                                 possible = false;

                                 break;

                         }

                 }

                 if (possible)

                         flag = true;

                 return;

        }

 

        for (int i = y; i < H; i++)

                 for (int j = 1; j < N; j++)

                         //두 가로선이 연속하거나 서로 접하면 안된다

                         if (!ladder[i][j - 1] && !ladder[i][j] && !ladder[i][j + 1])

                                 {

                                          ladder[i][j] = true;

                                          DFS(i, cnt + 1);

                                          ladder[i][j] = false;

                                 }

        return;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M >> H;

 

        for (int i = 0; i < M; i++)

        {

                 int y, x;

                 cin >> y >> x;

                 //(y-1)번째 col에서 x ~ (x+1)를 이어주는 사다리

                 ladder[y - 1][x] = true;

        }

 

        for (int i = 0; i <= 3; i++)

        {

                 ladderCnt = i;

                 DFS(0, 0);

                 if (flag)

                 {

                         cout << ladderCnt << "\n";

                         return 0;

                 }

        }

        cout << -1 << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~