2931 가스관

M,Z위치 찾아서 queue에 넣어주고 흘러갈 수 있는 길을 찾는다.

찾으면 방향을 설정하고 다시 큐에 넣고 흐름을 계속 타다가 끊어지는곳을 발견하면 break.

해당 위치에서 사방의 파이프 형태를 보고 어떤 파이프가 와야하는지 결정한다.

#include <stdio.h>
#include <queue>
using namespace std;
 
struct p {
    int x, y, w;
    p(int x, int y, int w) : x(x), y(y), w(w) {}
};
 
queue<p> q;
 
int r, c, dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 }, tx, ty;
 
// r d l u 순(시계방향). checker[][2], [3]은 각각 진행방향에서 좌회전, 우회전 하는 순서로 넣어놓는다.
char checker[4][6] = { { '-', '+', '3', '4', 'M', 'Z' },
{ '|', '+', '2', '3', 'M', 'Z' },
{ '-', '+', '1', '2', 'M', 'Z' },
{ '|', '+', '4', '1', 'M', 'Z' } };
char m[26][27];
 
bool check(int x, int y, int w) {
    if (w == -1) {    // M or Z
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            for (int j = 0; j < 4; j++) {
                if (m[nx][ny] == checker[i][j]) {
                    if (!(j == 0 || j == 1)) 
                        i = (i + 3 - (j % 2) * 2) % 4;
                    q.push({ nx,ny,i });
                    return false;
                }
            }
        }
    }
    else {            // else
        int nx = x + dx[w], ny = y + dy[w], nw;
        bool f = false;
        for (int i = 0; i < 4; i++) {
            if (m[nx][ny] == checker[w][i]) {
                if (i == 0 || i == 1) 
                    nw = w;        // 현재 방향을 그대로 유지하는 경우
                else 
                    nw = (w + 3 - (i % 2) * 2) % 4;    // 휘는경우
                q.push({ nx,ny,nw });
                return false;
            }
        }
        tx = nx, ty = ny;
        return true;                                // 타겟 찾음
    }
    return false;
}
 
int main() {
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; i++) {
        scanf("%s", &m[i]);
        for (int j = 0; j < c; j++) if (m[i][j] == 'M' || m[i][j] == 'Z') 
            q.push({ i,j,-1 });
    }
 
    while (!check(q.front().x, q.front().y, q.front().w))
        q.pop();        // 물 흘려보기
        
    int cnt = 0;
    bool ch[4] = { false, };
 
    for (int i = 0; i < 4; i++) {
        int nx = tx + dx[i], ny = ty + dy[i];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
        for (int j = 0; j < 6; j++) if (m[nx][ny] == checker[i][j]) 
            ch[i] = true;        // i방향으로 뚫려있다는 뜻
        cnt += ch[i];
    }
 
    char res;
    // 주변 모양 보고 판단
    if (cnt == 4) res = '+';
    else {
        if      (ch[0] & ch[2]) res = '-';
        else if (ch[0] & ch[1]) res = '1';
        else if (ch[0] & ch[3]) res = '2';
        else if (ch[1] & ch[3]) res = '|';
        else if (ch[1] & ch[2]) res = '4';
        else                    res = '3';
    }
 
    printf("%d %d %c", tx + 1, ty + 1, res);
    return 0;
}