[백준 1584] 게임

A. 접근법

우선순위 큐를 이용한 BFS로 문제해결을 하였다. 잃은 생명 값을 최소인 것을 계속해서 pop하며 탐색하는 방법이다. 문제 해결 후 검색해보니 이 풀이방법이 '0-1BFS'라고 생각이 들었다.

B. 구현

class cmp {
public:bool operator ()(const vector& p1, const vector& p2) {
if(p1[2] < p2[2])
return false;
else
return true;
}
};

이 부분이 잃은 생명의 최소인 값을 계속해서 pop을 하기 위한 비교부분이다. '0-1BFS'에서는 자료구조를 deque를 사용하면서 만약에 잃은 목숨이 현재보다 커지면 deque의 push_back을 이용하고 같다면 push_front를 이용한다 잃은 생명의 값이 줄어들지는 않는다. (줄어들어도 push_front를 하면 다음에 pop의 대상이 되기 때문에 문제는 없다.)

C. 코드

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
int T, N, M;
int table[501][501];
bool visit[501][501];
int answer;
//queue<vector<int>> q;
class cmp {
public:bool operator ()(const vector<int>& p1, const vector<int>& p2) {
        if(p1[2] < p2[2])
            return false;
        else
            return true;
}
};
priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
void bfs() {
    while(!pq.empty()) {
        int x = pq.top()[0];
        int y = pq.top()[1];
        int z = pq.top()[2];
        pq.pop();
        //cout << x << " " << y << " " << z << endl;
        if(x == 500 && y == 500) {
            if(z < answer)
                answer = z;
            continue;
        }
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= 0 && nx <= 500 && ny >= 0 && ny <= 500 && table[nx][ny] != 2 && !visit[nx][ny]) {
                if(table[nx][ny] == 0) {
                    visit[nx][ny] = true;
                    pq.push(vector<int> {nx, ny, z});
                }
                else if(table[nx][ny] == 1) {
                    visit[nx][ny] = true;
                    pq.push(vector<int> {nx, ny, z+1});
                }
                else {}
            }
        }
    }
}
int main() {
    //scanf("%d", &T);
    T = 1;
    for(int tc = 0; tc < T; tc++) {
        scanf("%d", &N);
        memset(table, 0, sizeof(int)*501*501);
        memset(visit, 0, sizeof(bool) * 501 *501);
        answer = 9999999;
        for(int i = 0; i < N; i++) {
            int a, b, c, d;
            scanf("%d %d %d %d", &a, &b, &c, &d);
            if(a > c) {
                int tmp = a;
                a = c;
                c = tmp;
            }
            if(b > d) {
                int tmp = b;
                b = d;
                d = tmp;
            }
            for(int x = a; x <= c; x++) {
                for(int y = b; y <= d; y++) {
                    table[x][y] = 1;
                }
            }
        }
        scanf("%d", &M);
        for(int i = 0; i < M; i++) {
            int a, b, c, d;
            scanf("%d %d %d %d", &a, &b, &c, &d);
            if(a > c) {
                int tmp = a;
                a = c;
                c = tmp;
            }
            if(b > d) {
                int tmp = b;
                b = d;
                d = tmp;
            }
            for(int x = a; x <= c; x++) {
                for(int y = b; y <= d; y++) {
                    table[x][y] = 2;
                }
            }
        }
        visit[0][0] = true;
        pq.push(vector<int> {0,0,0});
        bfs();
        if(answer == 9999999)
            cout << "-1" << endl;
        else
            cout << answer << endl;
    }
    return 0;
}

D. 결과