[백준 2931] 가스관

[백준 2931] 가스관

문제 링크

#include "header.h"
using namespace std;
int R, C;
char board[30][30];
int dir;

//상 하 좌 우
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
pair<int, int> start;
void input() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> board[i][j];

            if (board[i][j] == 'M') {
                start = {i, j};
            }

        }
    }
}
void addPipe(int x, int y){
    
    int dir_check[4] = {0, };
    vector<char> pipe = {'|', '-', '+', '1', '2', '3', '4'};

    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(board[nx][ny] == '.' || nx < 0 || ny < 0 || nx >= R || ny >= C) continue;

        if((i == 0) && (board[nx][ny] == '|' || board[nx][ny] == '+'
                        || board[nx][ny] == '1' || board[nx][ny] == '4')){
            dir_check[i] = 1;
        }else if((i == 1) && (board[nx][ny] == '|' || board[nx][ny] == '+'
                        || board[nx][ny] == '2' || board[nx][ny] == '3')){
            dir_check[i] = 1;
        }else if((i == 2) && (board[nx][ny] == '-' || board[nx][ny] == '+'
                        || board[nx][ny] == '1' || board[nx][ny] == '2')){
            dir_check[i] = 1;
        }else if((i == 3) && (board[nx][ny] == '-' || board[nx][ny] == '+'
                        || board[nx][ny] == '3' || board[nx][ny] == '4')){
            dir_check[i] = 1;
        }
    }

    char ret;

    if(dir_check[0] && dir_check[1] && dir_check[2] && dir_check[3]) ret = '+';
    else if(dir_check[0] && dir_check[1]) ret = '|';
    else if(dir_check[1] && dir_check[2]) ret = '4';
    else if(dir_check[2] && dir_check[3]) ret = '-';
    else if(dir_check[0] && dir_check[3]) ret = '2';
    else if(dir_check[1] && dir_check[3]) ret = '1';
    else if(dir_check[0] && dir_check[2]) ret = '3';

    cout << x + 1 << ' ' << y + 1 << ' ' << ret << endl;
}

void findDot(int x, int y, int dir){

    if(board[x][y] == '.'){
        // found
        addPipe(x, y);
        return;
    }

    int nx = x + dx[dir];
    int ny = y + dy[dir];

	if (dir == 0) {
		if (board[nx][ny] == '1') dir = 3;
		else if (board[nx][ny] == '4') dir = 2;
	}
	else if (dir == 1) {
		if (board[nx][ny] == '2') dir = 3;
		else if (board[nx][ny] == '3') dir = 2;
	}
	else if (dir == 2) {
		if (board[nx][ny] == '1') dir = 1;
		else if (board[nx][ny] == '2') dir = 0;
	}
	else if (dir == 3) {
		if (board[nx][ny] == '3') dir = 0;
		else if (board[nx][ny] == '4') dir = 1;
	}

	findDot(nx, ny, dir);
    return;
}
void solve() {

    for (int i = 0; i < 4; i++) {
        //상하좌우 넣기
        int nx = dx[i] + start.first;
        int ny = dy[i] + start.second;

        if(nx == start.first && ny == start.second) continue;
        if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
        if (board[nx][ny] != '.') {
            dir = i;
        }
    }

    findDot(start.first, start.second, dir);

}
int main() {
    input();
    solve();
    return 0;
}

• dfs로 푸는 문제
• 처음에 접근했던 방식은 점을 bfs로 찾기 -> 찾은 점에 모든 파이프 대입 -> 다시 bfs 돌려서 Z에 도달하면 정답

• 이런식으로 접근 했는데 너무 코드가 길어지고 방향을 체크하는데에 문제가 생겨서 다른 분의 코드를 참고하였다.

• M과 Z는 단 한개의 블록만 붙어있으므로, 4방향을 탐색 하여 붙은 방향이 어디인지 확인한다.
• dfs로 파이프를 판별하면서 파이프를 따라 이동한다.
• 이 때 .을 만나게 되면, 파이프를 연결한다.
• 파이프를 연결하는 과정은 해당 .의 4방향의 파이프에 의해서 결정 된다.
• dir_check라는 크기 4의 배열로 어떤 방향이랑 파이프가 연결 돼야 하는지 확인한다.
• check가 된 부분으로 빠진 파이프를 판별한다.