2931번 가스관

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

처음에 제출했을 때, 틀렸었다.

이유는 알고보니, 

또, 불필요한 블록이 존재하지 않는다. 즉, 없어진 블록을 추가하면, 모든 블록에 가스가 흐르게 된다.

라는 조건을 생각하지 못 했다. 사실 지문을 끝까지 안 읽고, 바로 풀기 시작했었다.

하여튼, 바로 조건을 고려하고 살짝 고치니 통과하였다.

내 생각에 이 문제의 핵심은 삼중배열(visit), 이중배열(block)이다.

visit[행][열][방향(d)] : 방향이 d인 상태에서 (행, 열)의 칸을 방문했는지의 여부

→ 예시처럼 '+'인 가스관에서 '+'의 정가운데인 곳을 다시 방문할 수 있기 때문에 삼중배열을 활용하였다.

block[가스관 모양][원래의 방향 d] (= num(새로운 방향)) : 방향이 원래 d인 곳에서 해당 가스관으로 들어올 때는 방향이 num으로 바뀐다.

-1일 때는 당연히 해당 지점에서 다음 가스관으로 통과하지 못 하는 경우이므로, bfs에서 활용한다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 130
 
bool visit[Max][Max][4], flow[Max][Max];
int block[Max][Max];
int R, C, mr, mc;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 }; // →(0) ↓(1) ←(2) ↑(3)
char m[Max][Max];
vector<char> vc = { '|', '-', '+', '1', '2', '3', '4' };
vector<pair<int, int> > v;
 
bool chk()
{
    for (auto i : v) {
        if (!flow[i.first][i.second]) {
            return false;
        }
    }
    return true;
}
 
bool bfs()
{
    memset(flow, false, sizeof(flow));
    memset(visit, false, sizeof(visit));
    queue<tuple<int, int, int> > tq;
    for (int i = 0; i < 4; i++) {
        visit[mr][mc][i] = true;
        tq.push({ mr, mc, i });
    }
    while (!tq.empty()) {
        int tqs = tq.size();
        while (tqs--) {
            int r = get<0>(tq.front());
            int c = get<1>(tq.front());
            int d = get<2>(tq.front());
            tq.pop();
            if (m[r][c] == 'Z' && chk()) return true;
            for (int i = 0; i < 4; i++) {
                if (i == d) {
                    int y = r + dy[i];
                    int x = c + dx[i];
                    if (y < 0 || y >= R || x < 0 || x >= C || m[y][x] == '.' || block[m[y][x]][d] == -1 || visit[y][x][block[m[y][x]][d]]) continue;
                    visit[y][x][block[m[y][x]][d]] = true;
                    flow[y][x] = true;
                    tq.push({ y, x, block[m[y][x]][d] });
                }            
            }
        }
    }
    return false;
}
 
int main() 
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    for (int i = 0; i < Max; i++) {
        for (int j = 0; j < Max; j++) {
            block[i][j] = -1;
        }
    }
    block['|'][1] = 1;
    block['|'][3] = 3;
    block['-'][0] = 0;
    block['-'][2] = 2;
    block['+'][0] = 0;
    block['+'][1] = 1;
    block['+'][2] = 2;
    block['+'][3] = 3;
    block['1'][2] = 1;
    block['1'][3] = 0;
    block['2'][1] = 0;
    block['2'][2] = 3;
    block['3'][0] = 3;
    block['3'][1] = 2;
    block['4'][0] = 1;
    block['4'][3] = 2;
    block['Z'][0] = 0;
    block['Z'][1] = 1;
    block['Z'][2] = 2;
    block['Z'][3] = 3;
    scanf("%d %d", &R, &C);
    getchar();
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
            if (m[i][j] == 'M') {
                mr = i; mc = j;
            }
            if (m[i][j] != '.' && m[i][j] != 'M' && m[i][j] != 'Z') {
                v.push_back({ i, j });
            }
        }
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (m[i][j] == '.') {
                v.push_back({ i, j });
                for (auto c : vc) {
                    m[i][j] = c;
                    if (bfs()) {
                        printf("%d %d %c\n", i + 1, j + 1, c);
                        return 0;
                    }
                }
                v.pop_back();
                m[i][j] = '.';
            }
        }
    }
 
    return 0;
}