Baekjoon 2564번 경비원

문제

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

걸린 시간

01 : 24 : 08

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int w, h;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
vector<vector<int>> block;
vector<vector<vector<int>>> visited;

struct node{
    int y, x, d;
    node(int y, int x, int d){
        this->y = y;
        this->x = x;
        this->d = d;
    }
};

void bfs(int y, int x, int d){
    queue<node> q;
    if(0 <= d && d < 2){
        q.push(node(y, x, 2));
        q.push(node(y, x, 3));
        visited[2][y][x] = 1;
        visited[3][y][x] = 1;
    }
    else{
        q.push(node(y, x, 0));
        q.push(node(y, x, 1));
        visited[0][y][x] = 1;
        visited[1][y][x] = 1;
    }
    int depth = 0;
    while(!q.empty()){
        depth++;
        int size = q.size();
        for(int i = 0; i < size; i++){
            int cy = q.front().y;
            int cx = q.front().x;
            int cd = q.front().d;
            q.pop();
            if((cy == 0 && cx == 0) || (cy == h-1 && cx == 0) || (cy == 0 && cx == w-1) || (cy == h-1 && cx == w-1)){
                if(0 <= cd && cd < 2){
                    for(int j = 2; j < 4; j++){
                        int ny = cy+dy[j];
                        int nx = cx+dx[j];
                        if(0 <= ny && ny < h && 0 <= nx && nx < w){
                            if(!visited[j][ny][nx]){
                                visited[j][ny][nx] = depth;
                                q.push(node(ny, nx, j));
                            }
                        }
                    }
                }
                else{
                    for(int j = 0; j < 2; j++){
                        int ny = cy+dy[j];
                        int nx = cx+dx[j];
                        if(0 <= ny && ny < h && 0 <= nx && nx < w){
                            if(!visited[j][ny][nx]){
                                visited[j][ny][nx] = depth;
                                q.push(node(ny, nx, j));
                            }
                        }
                    }
                }
            }
            else{
                int ny = cy+dy[cd];
                int nx = cx+dx[cd];
                if(0 <= ny && ny < h && 0 <= nx && nx < w){
                    if(!visited[cd][ny][nx]){
                        visited[cd][ny][nx] = depth;
                        q.push(node(ny, nx, cd));
                    }
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> w >> h;
    w++; h++;
    block.resize(h, vector<int>(w, 0));
    visited.resize(4, vector<vector<int>>(h, vector<int>(w, 0)));
    int s;
    cin >> s;
    vector<pair<int, int>> shop(s);
    int direction, distance; 
    for(int i = 0; i < s; i++){
        cin >> direction >> distance;
        if(direction == 1) shop[i] = make_pair(0, distance);
        if(direction == 2) shop[i] = make_pair(h-1, distance);
        if(direction == 3) shop[i] = make_pair(distance, 0);
        if(direction == 4) shop[i] = make_pair(distance, w-1);
    }
    cin >> direction >> distance;
    if(direction == 1) bfs(0, distance, 0);
    if(direction == 2) bfs(h-1, distance, 1);
    if(direction == 3) bfs(distance, 0, 2);
    if(direction == 4) bfs(distance, w-1, 3);
    int ans = 0;
    for(int i = 0; i < shop.size(); i++){
        int y = shop[i].first;
        int x = shop[i].second;
        int tmp = INF;
        for(int j = 0; j < 4; j++)
            if(visited[j][y][x] > 0)
                tmp = min(tmp, visited[j][y][x]);
        ans += tmp;
    }
    cout << ans << "\n";
    return 0;
}

좌표평면으로 표현된 직사각형 모양의 블록을 2차원 배열의 좌표로 알맞게 옮기고, 모서리에서의 방향 전환 처리를 잘 해주는것이 관건이다.