Baekjoon 2931번 가스관

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

int r, c;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
vector<pair<int, int>> MZ, pipe;
vector<vector<int>> visited;
vector<vector<char>> europe;
map<int, char> block;
node ans(0, 0, 0);

void solve(){
    queue<node> q;
    for(int i = 0; i < MZ.size(); i++){
        int y = MZ[i].first;
        int x = MZ[i].second;
        for(int j = 0; j < 4; j++){
            int ny = y+dy[j];
            int nx = x+dx[j];
            if(0 <= ny && ny < r && 0 <= nx && nx < c){
                if(europe[ny][nx] == '.') continue;
                switch(europe[ny][nx]){
                    case '|':
                    case '+':
                    case '-':
                        q.push(node(ny, nx, j));
                        break;
                    case '1':
                        if(j == 0) q.push(node(ny, nx, 3));
                        else q.push(node(ny, nx, 1));
                        break;
                    case '2':
                        if(j == 1) q.push(node(ny, nx, 3));
                        else q.push(node(ny, nx, 0));
                        break;
                    case '3':
                        if(j == 3) q.push(node(ny, nx, 0));
                        else q.push(node(ny, nx, 2));
                        break;
                    case '4':
                        if(j == 3) q.push(node(ny, nx, 1));
                        else q.push(node(ny, nx, 2));
                        break;
                }
            }
        }
    }
    while(!q.empty()){
        int y = q.front().y;
        int x = q.front().x;
        int d = q.front().d;
        q.pop();
        visited[y][x] = 1;
        int ny = y+dy[d];
        int nx = x+dx[d];
        switch(europe[ny][nx]){
            case '.':
                ans.y = ny;
                ans.x = nx;
                ans.d += 1<<d;
                break;
            case '|':
            case '+':
            case '-':
                q.push(node(ny, nx, d));
                break;
            case '1':
                if(d == 0) q.push(node(ny, nx, 3));
                else q.push(node(ny, nx, 1));
                break;
            case '2':
                if(d == 1) q.push(node(ny, nx, 3));
                else q.push(node(ny, nx, 0));
                break;
            case '3':
                if(d == 3) q.push(node(ny, nx, 0));
                else q.push(node(ny, nx, 2));
                break;
            case '4':
                if(d == 3) q.push(node(ny, nx, 1));
                else q.push(node(ny, nx, 2));
                break;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r >> c;
    visited.resize(r, vector<int>(c, 0));
    europe.resize(r, vector<char>(c));
    for(int y = 0; y < r; y++){
        for(int x = 0; x < c; x++){
            cin >> europe[y][x];
            if(europe[y][x] == 'M' || europe[y][x] == 'Z'){
                MZ.push_back(make_pair(y, x));
            }
            else if(europe[y][x] == '.'){
                // do nothing
            }
            else{
                pipe.push_back(make_pair(y, x));
            }
        }
    }
    block[3] = '|';
    block[12] = '-';
    block[15] = '+';
    block[5] = '1';
    block[6] = '2';
    block[10] = '3';
    block[9] = '4';
    solve();
    for(int i = 0; i < pipe.size(); i++){
        int y = pipe[i].first;
        int x = pipe[i].second;
        if(!visited[y][x]){
            cout << ans.y+1 << " " << ans.x+1 << " +\n";
            return 0;
        }
    }
    cout << ans.y+1 << " " << ans.x+1 << " " << block[ans.d] << "\n";
    return 0;
}

문제의 조건에서 시작(모스크바)과 끝(자그레브)이 하나의 블록과 인접해 있는 입력만 주어진다고 한다. 해커가 시작과 끝 지점과 연결되어 있는 블록을 지우는 경우는 없다는 뜻으로 해석할 수 있다.

또 불필요한 블록이 존재하지 않기 때문에 모스크바와 자그레브에서 시작하여 블록의 모양대로 가스의 진행 방향을 결정해주면 된다. 블록이 끝나는 지점이 해커가 지운 블록이 될 것이고 시작과 끝으로부터 진행된 가스의 두 방향으로 어떤 블록이 있었는지를 알아낼 수 있다.

이 때 해커가 + 블록을 제거한 경우는 가스가 한번도 흐르지 않은 블록이 있는지를 검사하면 확인할 수 있다.

가스의 흐름은 큐를, 없어진 블록의 계산과 출력은 비트마스크와 맵을 사용하여 구현했다.