[C언어] 15684. 사다리 조작

정답률에 비해 나름 쉽게 풀었던 문제, 정답률이 전부가 아님을 깨달았음에도..정답률 낮으면 일단 쫄고본다.ㅜ,ㅠ

접근법

1. 배열에 세로 사다리를 i*2씩 해서 배열에 표시해준다. ex) 10101 요런식으로

2. 10101 의 배열에 입력된 사다리를 0 사이사이에 넣어준다.

3. 사다리의 개수를 0~3개까지 전부 따져주어여 하므로, 개수를 늘려가며 탐색을 해주며, 정답이 존재하면 바로 break걸고 나온다.

4. 연구소와 같이 사다리 사이의 0에 사다리를 모든 경우의 수에 맞게 넣어준다.

5. 0~3개의 주사위가 가로로 놓아지면, 시작과 끝이 같은지 체크! 

#include <stdio.h>
#include <string.h>
 
int map[50][50];
int visit[50][50];
int N, H, M, ans;
int dx[] = { 1,-1,0 };
int dy[] = { 0,0,1 };
 
 
int down(int y, int x, int xxx)
{
    if (y == H + 1)
    {
        if (x == xxx)
            return 1;
        else
            return 0;
    }
    int Ret = 0;
 
    for (int i = 0; i < 3; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (xx <= 0 || xx > N * 2)
            continue;
 
        if (map[yy][xx] != 0 && visit[yy][xx] == 0)
        {
            visit[yy][xx] = 1;
            Ret = down(yy, xx, xxx);
            visit[yy][xx] = 0;
            return Ret;
        }
    }
    return Ret;
}
 
void DFS(int y, int x, int d, int n)
{
 
    if (d == n)
    {
        int Flag = 1;
 
        for (int i = 0; i < N; i++)
        {
            visit[1][1 + i * 2] = 1;
            if (down(1, 1 + i * 2, 1 + i * 2) == 0)
            {
                Flag = 0;
                visit[1][1 + i * 2] = 0;
                break;
            }
            visit[1][1 + i * 2] = 0;
        }
 
        if (Flag)
        {
            if (ans > n)
            {
                ans = n;
            }
        }
 
        return;
    }
 
 
    for (int a = y; a <= H; a++)
    {
        for (int b = x; b < N; b++)
        {
            if (map[a][b * 2] != 0)
                continue;
 
            map[a][b * 2] = 1;
            DFS(a, b, d + 1, n);
            map[a][b * 2] = 0;
        }
        x = 1;
    }
 
    return;
}
 
int main()
{
    ans = 9999999;
    scanf("%d %d %d", &N, &M, &H);
 
    for (int i = 0; i < N; i++)
        for (int j = 1; j <= H + 1; j++)
            map[j][1 + i * 2] = 2;
 
    int a, b;
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d", &a, &b);
        map[a][b * 2] = 2;
    }
 
    for (int n = 0; n <= 3; n++)
    {
        DFS(1, 1, 0, n);
 
        if (ans != 9999999)
            break;
    }
 
    if (ans == 9999999)
    {
        printf("-1\n");
        return 0;
    }
 
    printf("%d\n", ans);
 
    return 0;
}