14923 미로 탈출

 

벽을 한 번 부술 수 있다는 조건이 너무 어려웠다ㅠㅠㅠ

 

이걸 어떻게 해야할지 도저히 감을 못 잡아서 시간 초과할 거 알면서 그냥 생각나는대로 구현했음

 

벽마다 원점 - 벽, 벽 - 끝점 까지 거리를 각각 구한 후 더한 값을 비교했음

 

물론 시간초과났다,,ㅎㅎ 벽마다 n * m번 도니깐 그 제곱번만큼 더 돌겠지..

 

----

 

북님 풀이보고 다시 구현했는데 벽에 대한 상태값도 추가를 해줬다.

 

(x, y, t) = 현재 (x, y) 위치에 있음. t = 0이면 벽부수기 사용 안 하고 도달한 경우 t = 1이면 벽 부수기 사용하고 도달한 경우

 

(hx, hy, 0) 에서 (ex, ey, 0) 혹은 (ex, ey, 1)에 도달하면 조건을 만족한다. 두 정점 중 도달 거리가 짧은 것을 출력하면 된다. 

 

하지만 머리로 이해하는 것과 구현하는 건 별개의 문제였다...

 

이게 두 개를 동시에 관리한다는게 정말 안 와닿았음

 

공간은 하나인데?? 레이어를 두 개로 관리한다고???

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int v[1005][1005];
bool visited[1005][1005][2];
int h[1005][1005][2];

int n, m;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

struct maze {
    int x, y, z;
};

int     main()
{
    int sx, sy, ex, ey;

    cin >> n >> m >> sx >> sy >> ex >> ey;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> v[i][j];
        }
    }

    queue<maze> Q;
    Q.push({ sx, sy, 0 });
    visited[sx][sy][0] = true;

    int ans = -1;
    while (!Q.empty())
    {
        maze curr = Q.front();
        Q.pop();

        if (curr.x == ex && curr.y == ey)
        {
            ans = h[curr.x][curr.y][curr.z];
            break;
        }

        for (int i = 0; i < 4; i++)
        {
            maze next;
            next.x = curr.x + dx[i];
            next.y = curr.y + dy[i];
            next.z = curr.z;

            if (next.x <= 0 || n < next.x)
                continue;
            if (next.y <= 0 || m < next.y)
                continue;

            if (v[next.x][next.y] == 1)
            {
                if (next.z == 1)
                    continue;
                else
                    next.z = 1;
            }

            if (visited[next.x][next.y][next.z] == false)
            {
                visited[next.x][next.y][next.z] = true;
                h[next.x][next.y][next.z] = h[curr.x][curr.y][curr.z] + 1;
                Q.push({ next.x, next.y, next.z });
            }
        }
    }

    cout << ans;

    return 0;
}

 

구현은 어찌저찌 했다ㅠ 4시간 정도 고민한듯

 

다 짜고 나니깐 이런 구조구나~ 이해가 가긴 한다.

 

처음 짤 때 어느 부분이 어려웠냐면 dist를 t = 1, t = 0일 경우 전부 다 채워넣어서 x == ex && y == ey이면 dist[x][y][0] 이랑 dist[x][y][1]이랑 길이가 더 짧은거를 비교해서 넣어야 한다고 생각했음

 

그래서 dist[][][0]이랑 dist[][][1]을 전부 다 채워넣어야 하니 시작할 때 dist[][][1]을 어떻게 넣어야 하는지 막혔었다

 

도저히 생각 안 나서 다른사람 풀이 보고 힌트 얻었다. 

 

저 상태를 큐에 넣을 때 쓰는구나ㅋㅋㅋ

 

큐의 상태값이 1이면 이전에 벽을 뚫은 경우이고 큐의 상태값이 0이면 이전에 벽을 안 뚫었으니 벽을 뚫을 수 있다.

 

그리고 h값도 굳이 다 채울 필요 없이 1이 되면 그 때 h[0]에다 +1만 해주면 되는구나