[C언어] 2206. 벽 부수고 이동하기

이건...조만간 틀린 답안이 될 것이다.

현재는 맞았지만!!!왜냐하면 테케가 빈약했기 떄문이다!!!!!

나는 가능한 모든 벽을 하나씩 부순 후, 각각에 대하여 BFS(백트랙킹)를 해주었다. 그리고 이 중에서 최솟값을 출력해주었는데..

이렇게 하면 시간 복잡도가 맵의 크기를 1000으로 두면 1000*1000*1000*1000이다.!!!

결론은 틀린 답안~이지만 일단 올림.

#include <stdio.h>
#include <string.h>
 
#define MAX 999999
 
int M, N, MIN;
int MAP[1111][1111];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
 
 
void BACK(int y, int x, int len)
{
    if (MAP[y][x] == 1 || len > MIN)
        return;
 
    if (y == M && x == N)
    {
        if (len < MIN)
            MIN = len;
        return;
    }
 
    MAP[y][x] = 1;
 
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (xx > N || yy > M || xx <= 0 || yy <= 0)
            continue;
 
        if (MAP[yy][xx] == 0)
        {
            BACK(yy, xx, len + 1);
        }
 
    }
    MAP[y][x] = 0;
    return;
}
 
int main()
{
    scanf("%d %d", &M, &N);
 
    for (int i = 0; i <= 1011; i++)
    {
        for (int j = 0; j <= 1011; j++)
        {
            MAP[i][j] = 1;
        }
    }
 
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            scanf("%1d", &MAP[i][j]);
        }
    }
 
    MIN = MAX;
 
    BACK(1,1,1);//벽 부수지 않고 최단경로 찾기
 
    for (int i = 1; i <= M; i++)//벽 하나씩 부숴가면서 최단경로 찾기
    {
        for (int j = 1; j <= N; j++)
        {
            if (MAP[i][j] == 0 || (i == 1 && j == 1))
                continue;
 
            if ((MAP[i + 1][j] == 1 || i + 1 > M) &&
                (MAP[i][j + 1] == 1 || j + 1 > N) &&
                (MAP[i - 1][j] == 1 || i - 1 < 1) &&
                (MAP[i][j - 1] == 1 || j - 1 < 1))//0으로 바꾸었는데, 사방에 1이면 노 필요~
            {
                continue;
            }
 
            MAP[i][j] = 0;
            BACK(1, 1, 1);
            MAP[i][j] = 1;
        }
    }
 
    if (MIN == MAX)
    {
        printf("-1\n");
        return;
    }
    printf("%d\n", MIN);
 
    return 0;
}