[BFS/시뮬레이션] 1953. 탈주범 검거 (Java)

[SWEA] 1953. 탈주범 검거

📌 풀이 과정

BFS로 터널을 탐색하고, 이미 방문한 곳은 map[x][y] = -1 로 초기화 했다.

1. 처음 맨홀 위치에 있을 때 1시간 경과했기 때문에 큐에 시간 값으로 1을 넣는다.

2. 경과 시간 = L인 곳은 poll만 하고 더 이상의 탐색은 하지 않는다.

3. 터널 파이프 타입에 따라 가능한 방향만 탐색해야 한다.

4. 가능한 탐색 방향에서 다음 위치를 검사한다.
   1) 다음 위치가 터널 지도 범위를 벗어나지 않고
   2) 파이프가 있다면 현재 파이프와 연결할 수 있는 파이프인지 확인한다.
   적합한 파이프라면 map[nx][ny] = -1으로 방문 처리하고
   탈주범이 위치할 수 있는 장소이기에 카운팅 한다. answer++

🧐 연결 가능한 파이프인지 확인하기

7가지 파이프 방향과 각 파이프의 방향별로 연결 가능한 파이프 번호를 정의하는 것이 핵심이다.

• int[][] pipe
  현재 파이프에서 어느 방향으로 이동 가능한지를 정의한 배열
  예를 들어, pipe[0] = {0, 1, 2, 3}은 1번 파이프가 상(0), 하(1), 좌(2), 우(3) 방향으로 연결될 수 있다.

• int[][] connect
  이동하려는 방향에서 다음 파이프가 연결될 수 있는지를 확인하는 배열
  예를 들어, connect[0] = {1, 2, 5, 6}은 상(0) 방향에서 1, 2, 5, 6번 파이프와 연결될 수 있다.

// 방향: 상(0), 하(1), 좌(2), 우(3)
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    // 파이프 방향 정의 (상하좌우)
    static int[][] pipe = {
        {0, 1, 2, 3}, // 1번 파이프: 상하좌우
        {0, 1},       // 2번 파이프: 상하
        {2, 3},       // 3번 파이프: 좌우
        {0, 3},       // 4번 파이프: 상우
        {1, 3},       // 5번 파이프: 하우
        {1, 2},       // 6번 파이프: 하좌
        {0, 2}        // 7번 파이프: 상좌
    };

    // 방향별 연결 가능한 파이프 번호
    static int[][] connect = {
        {1, 2, 5, 6}, // 상
        {1, 2, 4, 7}, // 하
        {1, 3, 4, 5}, // 좌
        {1, 3, 6, 7}  // 우
    };

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 탈주범검거_1953 {

    static int count;
    static int N, M, R, C, L;
    static int[][] map;

    // 방향: 상(0), 하(1), 좌(2), 우(3)
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    // 파이프 방향 정의 (상하좌우)
    static int[][] pipe = {
        {0, 1, 2, 3}, // 1번 파이프: 상하좌우
        {0, 1},       // 2번 파이프: 상하
        {2, 3},       // 3번 파이프: 좌우
        {0, 3},       // 4번 파이프: 상우
        {1, 3},       // 5번 파이프: 하우
        {1, 2},       // 6번 파이프: 하좌
        {0, 2}        // 7번 파이프: 상좌
    };

    // 방향별 연결 가능한 파이프 번호
    static int[][] connect = {
        {1, 2, 5, 6}, // 상
        {1, 2, 4, 7}, // 하
        {1, 3, 4, 5}, // 좌
        {1, 3, 6, 7}  // 우
    };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 터널의 세로 크기
            M = Integer.parseInt(st.nextToken()); // 터널의 가로 크기
            R = Integer.parseInt(st.nextToken()); // 맨홀 뚜껑이 위치한 행 좌표
            C = Integer.parseInt(st.nextToken()); // 맨홀 뚜껑이 위치한 열 좌표
            L = Integer.parseInt(st.nextToken()); // 탈출 후 소요된 시간
            map = new int[N][M];
            count = 1;

            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < M; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            bfs(R, C);
            System.out.println("#" + t + " " + count);
        }
    }

    static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x, y, map[x][y], 1});
        map[x][y] = -1; // 방문 처리

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            x = cur[0];
            y = cur[1];
            int pipeType = cur[2];
            int time = cur[3]; // 경과된 시간

            if(time == L) continue; // 탈출 소요 시간이 된 경우 탐색 종료

            for(int d : pipe[pipeType - 1]) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                int nextPipeType;

                if(nx < 0 || nx >= N || ny < 0 || ny >= M || (nextPipeType = map[nx][ny]) <= 0) continue;

                if(isConnected(d, nextPipeType - 1)) {
                    q.offer(new int[] {nx, ny, nextPipeType, time + 1});
                    map[nx][ny] = -1;
                    count++;
                }
            }
        }
    }

    static boolean isConnected(int dir, int nextPipeType) {
        for(int connectPipe : connect[dir]) {
            if(connectPipe == nextPipeType + 1) {
                return true;
            }
        }
        return false;
    }
}

BFS로 접근해서 잘 풀어나갔지만, 다음 탐색할 파이프가 현재 파이프와 연결되는 파이프인지
확인하는 절차를 구현하는 것에 어려움을 느꼈다!