백준 2931번 가스관 - C++ 풀이

---

 

1. 모든 배관에 대해, 끊긴 길의 방향을 모두 찾는다.
2. 끊긴 모든 방향을 다시 이을 수 있는 배관의 위치와 종류를 찾는다.

 

1. 모든 배관에 대해, 끊긴 길의 방향을 모두 찾는다.

 모든 배관에 대해, 끊긴 길의 방향을 모두 찾아둔다. 아래와 같은 상황에서 (2,2)의 | 모양 배관을 보면, 아래 방향으로는 길이 끊겨있다. 이는 곧 (3,2)에서 윗방향으로 잇는 배관이 필요하다는 뜻이므로 기록해둔다. 마찬가지로 (4,2)의 | 모양 배관을 보면, 윗방향으로 길이 끊겨있다. (3,2)에서 아랫방향으로 잇는 배관이 필요하다는 뜻이다.

2. 끊긴 모든 방향을 다시 이을 수 있는 배관의 위치와 종류를 찾는다.

 딱 한 개의 배관만 제거했다고 했으므로, 배관이 필요한 칸은 한 개뿐이다. 해당 칸에 필요한 방향을 가지고 배관 모양을 알아내면 된다. 위의 예시를 다시 살펴보면, (3,2) 칸은 위와 아래를 잇는 배관이 필요하다. 따라서 | 모양 배관을 (3,2) 칸에 두면 된다. 

 

반응형

---

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;

int R, C, SR, SC;
string board[25];
vector<bool> not_connected[25][25];

char blocks[] = {'|', '-', '+', '1', '2', '3', '4'};
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, -1, 0, 1};
vector<bool> adjs[7] =
{
  {1, 0, 1, 0},
  {0, 1, 0, 1},
  {1, 1, 1, 1},
  {0, 0, 1, 1},
  {1, 0, 0, 1},
  {1, 1, 0, 0},
  {0, 1, 1, 0}
};

vector<bool> getAdjacent(int r, int c) {
    switch (board[r][c]) {
        case '|': return adjs[0];
        case '-': return adjs[1];
        case '+': return adjs[2];
        case '1': return adjs[3];
        case '2': return adjs[4];
        case '3': return adjs[5];
        case '4': return adjs[6];
    }
    
    return {};
}

void checkConnected(int r, int c) {
    auto adjs = getAdjacent(r, c);
    
    for (int i=0; i<4; i++) {
        if (!adjs[i]) continue;
        
        int adjr = r + dr[i];
        int adjc = c + dc[i];
        if (adjr < 0 || adjr >= R || adjc < 0 || adjc >= C) continue;
    
        if (board[adjr][adjc] == '.') not_connected[adjr][adjc][(i+2)%4] = true;
    }
}

char calcBlock(int r, int c) {
    for (int i=0; i<7; i++) {
        if (not_connected[r][c] == adjs[i]) return blocks[i];
    }
    
    return '?';
}

void solution() {
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            if (board[i][j] == '.') continue;
            if (board[i][j] == 'M' || board[i][j] == 'Z') continue;
            checkConnected(i, j);
        }
    }
    
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            for (int k=0; k<4; k++) {
                if (not_connected[i][j][k]) {
                    cout << i+1 << " " << j+1 << " " << calcBlock(i, j);
                    return;
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for (int i=0; i<25; i++) {
        for (int j=0; j<25; j++) {
            not_connected[i][j].resize(4);
        }
    }
    
    cin >> R >> C;
    for (int i=0; i<R; i++) {
        cin >> board[i];
        for (int j=0; j<C; j++) {
            if (board[i][j] == 'M') {
                SR = i;
                SC = j;
            }
        }
    }
    
    solution();

    return 0;
}