[백준/C++] 14923번: 미로탈출

 

이 문제같은 경우 map이 굉장히 컸다. 사실 바로 이전에 풀었던 문제인 연구소(sanghyu.tistory.com/72?category=1139260)와 유사해보여서 풀었는데, 연구소문제처럼 부르트포스로 풀었더니 시간초과가 났다. 사실 예상했던 결과긴 하지만 다른 방식이 생각나지 않아 그렇게 해봤던 것이다.. 그래서 내 힘으로 도저히 못풀겠어서 다른 분들이 풀었던 답안을 참고해서 공부하였다.

** 가중치1, 최단경로이므로 BFS로 풀어야함

 

아 그리고 또 실수 했던 부분은 시작점이 (1,1)부터여서 나도 1부터 for문을 돌려놓고 map은 1000을 limit으로 줬더니 당연히 틀린다... 1부터 시작할 거면 1001을 limit으로 했었어야 했는데^^

 

그래서 풀이 방법은 다음과 같다.

 

1) visit배열에 벽을 뿌수는 key를 가지고 있는지 아닌지를 나타내는 차원을 하나 더 추가한다. 

2) BFS를 돌린다. (queue에 담는 조건: map이 0이거나 1인데 key가 있거나)

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

int N, M;
int Hx, Hy;
int Ex, Ey;
int map[1001][1001];
int visit[1001][1001][2];

int dx[] = { 1,0,0,-1 };
int dy[] = { 0,1,-1,0 };
void bfs(int x, int y) {

    queue<pair<pair<int, int>, pair<int, int>>> q;
    q.push({ { x, y }, { 0, 1 } });
    while (!q.empty()) {

        int cx = q.front().first.first;
        int cy = q.front().first.second;
        int depth = q.front().second.first;
        int key = q.front().second.second;

        q.pop();

        if (cx == Ex && cy == Ey) {
            cout << depth;
            return;
        }

        if (visit[cx][cy][key]) continue;
        visit[cx][cy][key] = 1;

        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx <= 0 || nx > N || ny <= 0 || ny > M)continue;
            if (map[nx][ny] == 1 && key == 1)  q.push({ { nx, ny }, { depth + 1,0 } });
            if (map[nx][ny] == 0)  q.push({ { nx, ny }, { depth + 1, key } });

        }
    }

    cout << "-1";
    return;

}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;
    cin >> Hx >> Hy;
    cin >> Ex >> Ey;


    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }

    bfs(Hx, Hy);

    return 0;
}

 

 

시간초과 난 코드...

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

int N, M;
int Hx, Hy;
int Ex, Ey;
int map[1001][1001];
int visit[1001][1001];
vector<pair<int, int>> walls;
int temp;
int ans;


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


void init() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            visit[i][j] = 0;
        }
    }
}

int bfs(int x, int y) {

    queue<pair<pair<int, int>, int>> q;
    visit[x][y] = 1;
    q.push(make_pair(make_pair(x, y), 0));
    while (!q.empty()) {

        int cx = q.front().first.first;
        int cy = q.front().first.second;
        int cd = q.front().second;

        q.pop();

        if (cx == Ex && cy == Ey) {
            //cout << cd;
            return cd;
        }


        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx <= 0 || nx > N || ny <= 0 || ny > M)continue;
            if (map[nx][ny] == 0 && visit[nx][ny] == 0) {
                //cout << nx << "," << ny << endl;
                visit[nx][ny] = 1;
                q.push(make_pair(make_pair(nx, ny), cd + 1));
            }
        }
    }

    //cout << "-1";
    return -1;

}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;
    cin >> Hx >> Hy;
    cin >> Ex >> Ey;


    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 1)walls.push_back(make_pair(i, j));
        }
    }

    ans = bfs(Hx, Hy);
    init();

    for (int i = 0; i < walls.size(); i++) {
        int x_point = walls[i].first;
        int y_point = walls[i].second;


        map[x_point][y_point] = 0;

        /*
        cout << endl;
        for (int q = 1; q <= N; q++) {
            for (int w = 1; w <= M; w++) {
                cout << map[q][w] << " ";
            }
            cout << endl;
        }
        */






        temp = bfs(Hx, Hy);
        //cout << "ans: " << ans << ", temp: " << temp << endl;

        if (ans == -1 && temp != -1)ans = temp;
        if (ans != -1 && temp == -1)ans = ans;
        else ans = ans < temp ? ans : temp;

        //원상복구
        map[x_point][y_point] = 1;
        init();
    }

    cout << ans;

    return 0;
}