백준 1584번 게임 [C++]

 

https://www.acmicpc.net/problem/1584

1584번: 게임

#문제 간단 정리

0-1 bfs 문제

#문제 해결 방법

기존의 bfs 에서 

비용이 들지 않는 것을 먼저 우선순위를 두어 계산해주는 

0-1 bfs 를 활용하자

덱을 사용해서 

생명소모없이 지나갈 수 있는 안전지대를

덱의 앞으로 푸쉬하고

생명소모하는 위험지대를 

덱의 뒤로 푸쉬해서

우선순위에 차이를 둬서 탐색하도록 하면 된다

 

또한 주의해야될게 각 모서리 두 부분이 주어지는데

모서리에 따른 위험지대 처리에 주의하도록 하자

어느쪽에 있는 모서리인지 확인해야 한다

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <deque>
using namespace std;

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

void zoneSetting(vector<vector<int>>& zone, int y1, int y2, int x1, int x2, int type) {
    for (int i = min(y1, y2); i <= max(y1, y2); i++) {  
        for (int j = min(x1, x2); j <= max(x1, x2); j++) {
            zone[i][j] = type;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //0 안전 1 위험 2 죽음
    vector<vector<int>> zone(501, vector<int>(501, 0));
    vector<vector<bool>> visited(501, vector<bool>(501, false));

    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x1, y1, x2, y2;
        cin >> x2 >> y1 >> x1 >> y2;
        zoneSetting(zone, y1, y2, x1, x2, 1);
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int x1, y1, x2, y2;
        cin >> x2 >> y1 >> x1 >> y2;
        zoneSetting(zone, y1, y2, x1, x2, 2);
    }

    deque<pair<pair<int, int> , int>> d;
    d.push_back({ { 0, 0 } , 0 });
    visited[0][0] = true;
    int goalLife = 0;
    bool goal = false;

    while (!d.empty()) {
        int bx = d.front().first.first;
        int by = d.front().first.second;
        int life = d.front().second;
        if (bx == 500 && by == 500) {
            goal = true;
            goalLife = life;
            break;
        }

        d.pop_front();

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

            if (0 <= nx && nx <= 500 && 0 <= ny && ny <= 500 && !visited[nx][ny]) {
                visited[nx][ny] = true; 
                if (zone[nx][ny] == 0) {
                    d.push_front({ { nx, ny }, life });
                }
                else if (zone[nx][ny] == 1) {
                    d.push_back({ { nx, ny },life +1});
                }
            }
        }
    }

    if (goal) {
        cout << goalLife << '\n';
    }
    else {
        cout << -1 << '\n';
    }


    return 0;
}