[BaekJoon] 2931 가스관 :: monton

문제

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

풀이

이 문제는 dfs를 이용하여 visit으로 체크하면서 이동하는 방법을 사용

1. dfs를 이용하여 상하좌우 방향으로 이동 + visit으로 체크 (다시 0으로 만들지 않음)

1-1. 상하좌우 방향으로 이동할 때 checkdir 함수 (현재 가스관 모양으로 움직이게 도와주는 함수)를 만들어서 가능한 반향으로만 이동

2. 이동한 칸이 '.' 이면 원래 가스관이 존재 했던 곳이라 판단

2-1. 비트마스크를 사용하여 bit 변수에 이동 방향을 변수에 저장

3. '.'이면서 visit이 체크 된 곳의 좌표를 출력하고 bit에 맞는 가스관 모양 출력

이렇게 설정을하여 비트마스크에 적용

위와 같이 비트마스크 진행

코드

#include <iostream>
 
using namespace std;
 
int R, C;
char arr[26][26];
int visit[26][26];
int bit;
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
int checkdir(int x, int y,int n) {
    if (arr[x][y] == '|') if (n == 0 || n == 2) return 1;
    if (arr[x][y] == '-') if (n == 1 || n == 3) return 1;
    if (arr[x][y] == '+') if (1) return 1;
    if (arr[x][y] == '1') if (n == 1 || n == 2) return 1;
    if (arr[x][y] == '2') if (n == 0 || n == 1) return 1;
    if (arr[x][y] == '3') if (n == 0 || n == 3) return 1;
    if (arr[x][y] == '4') if (n == 2 || n == 3) return 1;
 
    return 0;
}
 
void dfs(int x, int y,int n) {
    if (x < 0 || x >= R || y < 0 || y >= C||arr[x][y]=='M' || arr[x][y] == 'Z') return;
    if (visit[x][y]&&arr[x][y]!='.') return;
 
    if (n != 5&&arr[x][y]=='.') bit |=(1<<n);

    visit[x][y] = 1;
    if (arr[x][y] == '.') return;
 
    for (int i = 0; i < 4; i++) {
        if (checkdir(x, y, i)) {
            dfs(x + dir[i][0], y + dir[i][1], i);
        }
    }
}
 
int main() {
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] != '.' && !visit[i][j]) dfs(i, j, 5);
        }
    }
 
    int flag = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] == '.' && visit[i][j]) {
                cout << i + 1 << " " << j + 1 << " ";
                flag = 1;
                break;
            }
        }
        if (flag) break;
    }
    
    if (bit == 5) cout << "|";
    if (bit == 10) cout << "-";
    if (bit == 15) cout << "+";
    if (bit == 9) cout << "1";
    if (bit == 12) cout << "2";
    if (bit == 6) cout << "3";
    if (bit == 3) cout << "4";
}