[BOJ/Java] 2931. 가스관

📌 [BOJ/Java] 2931. 가스관

• 문제 링크

---

💡 문제 해석

도시에는 여러 개의 가스관이 설치되어 있으며, 가스관은 일정한 패턴의 블록으로 이루어져 있다.
어느 날 하나의 블록이 사라지는 사고가 발생하여, 이를 찾아 원래의 블록을 복구해야 한다.

🔹 주어진 정보

• N × M 크기의 도시 지도 (.: 빈칸, + - | 1 2 3 4 M Z: 가스관)
• M: 가스가 시작되는 위치
• Z: 가스가 도착하는 위치

✅ 목표:
1️⃣ 사라진 블록의 위치를 찾아 출력
2️⃣ 해당 위치에 들어갈 올바른 블록 종류를 출력

---

📝 풀이 과정

1️⃣ 사라진 블록(.) 찾기

• 가스관을 따라가다가 연결이 끊긴 지점을 찾는다.

2️⃣ 사라진 블록이 가질 수 있는 형태 탐색

• + - | 1 2 3 4 중 올바른 블록을 결정
• 연결된 블록들의 방향을 고려하여 가능한 블록을 찾는다.

3️⃣ BFS를 활용한 가스관 탐색

• M에서 시작하여 가스관을 따라 이동하며 연결된 블록 탐색
• .을 만나는 순간 끊어졌으므로 사라진 블록의 위치 기록

---

💻 코드 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int R, C;
    static char[][] map;

    static final int[] dx = {-1, 1, 0, 0};  // 상, 하, 좌, 우
    static final int[] dy = {0, 0, -1, 1};

    static final int TOP = 0, BOTTOM = 1, LEFT = 2, RIGHT = 3;

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] input = in.readLine().split(" ");
        R = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);
        map = new char[R][C];

        for (int i = 0; i < R; i++) {
            map[i] = in.readLine().toCharArray();
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == '.' && check(i, j)) {
                    return;
                }
            }
        }
    }

    private static boolean check(int x, int y) {
        boolean[] connected = new boolean[4];

        if (isValid(x + dx[TOP], y + dy[TOP]) && canComeBottom(map[x + dx[TOP]][y + dy[TOP]])) {
            connected[TOP] = true;
        }
        if (isValid(x + dx[BOTTOM], y + dy[BOTTOM]) && canComeTop(map[x + dx[BOTTOM]][y + dy[BOTTOM]])) {
            connected[BOTTOM] = true;
        }
        if (isValid(x + dx[LEFT], y + dy[LEFT]) && canComeRight(map[x + dx[LEFT]][y + dy[LEFT]])) {
            connected[LEFT] = true;
        }
        if (isValid(x + dx[RIGHT], y + dy[RIGHT]) && canComeLeft(map[x + dx[RIGHT]][y + dy[RIGHT]])) {
            connected[RIGHT] = true;
        }

        char correctPipe = findCorrectPipe(connected);
        if (correctPipe != '?') {
            System.out.println((x + 1) + " " + (y + 1) + " " + correctPipe);
            return true;
        }

        return false;
    }

    private static char findCorrectPipe(boolean[] connected) {
        if (connected[TOP] && connected[BOTTOM] && connected[LEFT] && connected[RIGHT]) return '+';
        if (connected[TOP] && connected[BOTTOM]) return '|';
        if (connected[LEFT] && connected[RIGHT]) return '-';
        if (connected[BOTTOM] && connected[RIGHT]) return '1';
        if (connected[TOP] && connected[RIGHT]) return '2';
        if (connected[TOP] && connected[LEFT]) return '3';
        if (connected[BOTTOM] && connected[LEFT]) return '4';
        return '?';
    }

    private static boolean canComeTop(char c) {
        return c == '|' || c == '+' || c == '2' || c == '3';
    }

    private static boolean canComeBottom(char c) {
        return c == '|' || c == '+' || c == '1' || c == '4';
    }

    private static boolean canComeLeft(char c) {
        return c == '-' || c == '+' || c == '3' || c == '4';
    }

    private static boolean canComeRight(char c) {
        return c == '-' || c == '+' || c == '1' || c == '2';
    }

    private static boolean isValid(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }
}

---

⏱ 시간 복잡도 분석

• BFS 탐색 → O(N × M)
• 가능한 블록 탐색 → O(7 × 4) = O(28) (상수 시간)
• 총 시간 복잡도 → O(N × M), 충분히 해결 가능

---

🧐 느낀 점

✅ 양방향 연결을 고려하는 것이 중요했다.
✅ 올바른 블록을 찾을 때 모든 방향에서 연결 가능 여부를 체크해야 했다.
✅ 출력 좌표는 1부터 시작하므로 주의해야 했다.

🚀 디테일한 조건을 정확히 처리하는 것이 핵심인 문제였다! 😊