[백준_15684(사다리 조작)]

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

문제 설명

문제 풀이

• 최대 놓을 수 있는 사다리는 3 개 이므로 사다리를 놓는 경우의 수는 300^3이다. 사다리로 이동하는 경우의 수는 N * H임으로 최대 시간 복잡도는 (N H \ 300^3)으로 충분하다.

1. 사다리 놓기
   • 재귀를 사용하여 좌표 값에 3개의 사다리를 놓는다.
   • 만일 해당하는 좌표 [x][y]o r 그 다음 좌표[x][y+1] 가 이미 사다리라면 넘어간다.
   • 위에 조건이 아니라면 해당하는 좌표 [x][y]와 다음 좌표[x][y+1]에 사다리를 놓는다.
     • 이때 사다리의를 시작점인 y 값으로 저장하여 시작 사다리를 구분한다.
2. 사다리 이동
   • 해당하는 열을 기준으로 행을 탐색한다.
     • 시작점 열로 시작하여 해당 행에 사다리가 있는 지 탐색
     • 현재 기준점이 1 이거나 마지막 열이면
       • 1열이라면 =>2열로 , N열이라면 N-1로 이동한다.
     • 그 외경우 좌우로 사다리 확인
       • 왼쪽 사다리 인지 오른쪽 사다리가 인지 확인하고 해당 위치로 기준점 이동한다.
       • [i][start - 1] == p[i][start] or [i][start + 1] == [i][start]
   • 시작점과 도착점이 같다면 카운팅
3. 모든 결과가 시작점과 도착점이 일치하면 추가한 다리 횟수 저장

 

 

코드

#include <iostream>

using namespace std;

int N, M, H;

int p[31][11];
int ans = -1;

void go(int x, int cnt)
{

    int result = 0;
    for (int j = 1; j <= N; j++)
    {
        int start = j; //시작점 저장
        for (int i = 1; i <= H; i++)
        {

            if (p[i][start] == 0) //다리 없으면 넘어감
                continue;

            if (start == 1 || start == N)
            {
                //열이 1 이거나 마지막열이면,
                //(1열이라면 =>2열로 , N열이라면 N-1로 이동)
                start = (start == 1) ? start + 1 : (start - 1);
            }
            else
            {
                //그외경우 좌우로 사다리 확인
                if (p[i][start - 1] == p[i][start]) //사다리의 시작점이 같은 지 확인
                {
                    //왼쪽으로 부터 사다리가 이어질 경우,

                    start -= 1;
                }
                else if (p[i][start + 1] == p[i][start])
                {
                    //오른쪽으로 부터 사다리가 이어질 경우
                    start += 1;
                }
            }
        }

        if (start == j) //시작점과 도착점이 같다면 카운팅
        {
            result++;
        }
    }

    if (result == N)
    {
        //모든 결과가 시작점과 도착점이 일치하면 추가한 다리 횟수 저장

        if (ans == -1)
        {
            ans = cnt;
        }
        else
        {

            ans = min(ans, cnt);
        }

        return;
    }

    if (cnt == 3)
    {
        //3번 진행 후 종료

        return;
    }

    for (int i = x; i <= H; i++)
    {
        for (int j = 1; j < N; j++)
        {

            if (p[i][j] || p[i][j + 1])

            {
                //현재 위치나 그 다음 위치에 이미 있다면 넘어감
                continue;
            }
            else
            {
                //없다면,다음 열 까지 사다리 만듬

                p[i][j] = j;
                p[i][j + 1] = j;

                go(i, cnt + 1);
                p[i][j] = 0;
                p[i][j + 1] = 0;
            }
        }
    }
}

int main(void)
{

    cin >> N >> M >> H;

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

        int x, y;
        cin >> x >> y;

        p[x][y] = y;
        p[x][y + 1] = y;
        //다리 입력 받을시에 시작점을 넣어 구분
    }

    go(1, 0);
    cout << ans << '\n';

    return 0;
}