[C언어 ] 2665. 미로 만들기

음...최근에 업로드한 1600번 말이 되고픈 원숭이나 벽부수고 이동하기와 같이 풀었다.

다른 사람들은 어떻게 풀었는지 모르겠지만..위와 같은 방식이면 이렇게 정답률이 높을리가 없는데!!내가 어렵게 풀었나ㅋㅋㅋㅋ맞추기만 하면 되지!!!

접근법

1. 최악의 경우 맵 크기는 50*50이다. 벽이 출발, 도착 지점 말고 전부 벽이면 최대 100개의 돌을 부셔야 한다.

2. 1개 ~ 100개의 벽을 부술 수 있는 경우를 모두 고려해주었다. (삼성 기출 연구소와같이 벽을 조합으로 부수면 시간초과 남)

3. 그래서 최근에 풀었던 벽부수고 이동하기와 비슷한 느낌이라!! 같은 방식으로 풀기를 결정.

4. 최대 100개를 부순다고 생각하고 arr[101][50][50] 의 배열을 만들어준다.

5. 100은 0~100개의 벽을 부쉈을 때 상태의 BFS맵니다.

6. BFS를 하면서 목표지점까지 탐색하다 벽을 만나면 벽을 부순 카운트를 올리고 벽을 부순 상태의 배열에 visit처리를 해준다.

7. 가장 적게 벽을 부순 경우를 찾으며 break걸고 답을 출력.

설명 어렵

#include <stdio.h>
#include <string.h>
 
typedef struct 
{
    int y, x, g;
}point;
 
int map[60][60];
int N, ans, Q_Front = -1, Q_Back = -1;
point Q[100 * 50 * 50];
int visit[111][60][60] = { 0, };
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
int main()
{
    memset(map, -1, sizeof(map));
    scanf("%d", &N);
 
    ans = 60 * 60 * 60;
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            scanf("%1d", &map[i][j]);
 
    for (int k = 0; k <= 2 * N; k++)
    {
        memset(visit, 0, sizeof(visit));
        memset(Q, 0, sizeof(Q));
        Q_Back = Q_Front = -1;
 
        Q[++Q_Back].y = 1;
        Q[Q_Back].x = 1;
        Q[Q_Back].g = 0;
        visit[0][1][1] = 1;
 
        while (Q_Front != Q_Back)
        {
            int y = Q[++Q_Front].y;
            int x = Q[Q_Front].x;
            int g = Q[Q_Front].g;
 
            if (y == N && x == N)
            {
                printf("%d",g);
                return 0;
            }
 
            for (int i = 0; i < 4; i++)
            {
                int yy = y + dy[i];
                int xx = x + dx[i];
 
                if (map[yy][xx] == -1 || visit[g][yy][xx] == 1)
                    continue;
 
                if (map[yy][xx] == 1 && visit[g][yy][xx] == 0)
                {
                    Q[++Q_Back].y = yy;
                    Q[Q_Back].x = xx;
                    Q[Q_Back].g = g;
                    visit[g][yy][xx] = 1;
                }
                else if (map[yy][xx] == 0 && g + 1 <= k && visit[g + 1][yy][xx] == 0)
                {
                    Q[++Q_Back].y = yy;
                    Q[Q_Back].x = xx;
                    Q[Q_Back].g = g + 1;
                    visit[g + 1][yy][xx] = 1;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}