[SW Expert] [모의 SW 역량테스트] 1953번 탈주범 검거 (Java)

SW Expert [모의 SW 역량테스트] 1953번 탈주범 검거 : 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

 

 

bfs를 많이 해봐서 그런가 이제 이런 유형의 문제는 익숙한 듯하다.

Queue에 탈주범이 위치해 있는 좌표값을 넣는다.

탈주범이 방문했던 곳은 다시 넣지 않으므로, 탈주범이 해당 시간동안 가장 멀리 갈 수 있는 곳의 좌표가 들어가게 된다.

 

본 문제에서는 특이한 조건이 있었는데, 파이프의 종류에 따라 갈 수 있는 곳이 달라진다.

파이프를 연결하기 위해서 해당 위치에서 파이프가 연결된 곳의 정보를 status로 지정해줬다.

북쪽부터 시작하여 시계방향으로 0, 1, 2, 3을 지정했다.

예를 들어 2번 파이프인 경우, 북쪽과 남쪽만 연결되어 있기 때문에 status는 {1, 0, 1, 0}이 된다.

마찬가지로 4번 파이프인 경우엔 {1, 1, 0, 0}이 된다.

이러한 방식으로 인접 파이프와 연결된 곳만 찾아서 Queue에 담아주었다.

 

 

코드 

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

public class Main {
    private static int n, m, r, c, l, count;
    private static int[][] map;
    private static boolean[][] visit;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static boolean[][] status = {
            {true, true, true, true}, {true, false, true, false},
            {false, true, false, true}, {true, true, false, false},
            {false, true, true, false}, {false, false, true, true},
            {true, false, false, true}
    };

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

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            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];
            visit = new boolean[n][m];
            count = 0;

            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());
                }
            }

            solution();
            System.out.println("#" + t + " " + count);
        }
    }

    private static void solution() {
        Queue<Index> queue = new LinkedList<>();
        queue.add(new Index(r, c));
        visit[r][c] = true;
        int nx, ny;

        while (l-- > 0) {
            int len = queue.size();
            for (int t = 0; t < len; t++) {
                Index target = queue.poll();
                count++;

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

                    if (status[type - 1][i] && isValid(nx, ny)) { // 파이프가 뚫려 있는지, map 밖으로 나가지 않았는지
                        if (map[nx][ny] != 0 && !visit[nx][ny]) { // 인접 지역에 파이프가 있는지, 이전 방문한 곳인지
                            int nType = map[nx][ny];

                            if (status[nType - 1][(i + 2) % 4]) {
                                queue.add(new Index(nx, ny));
                                visit[nx][ny] = true; // 방문 처리
                            }
                        }
                    }
                }
            }
        }
    }

    private static boolean isValid(int x, int y) {
        if (x < 0 || y < 0 || x >= n || y >= m) return false;
        return true;
    }
}

class Index {
    int x;
    int y;

    public Index(int x, int y) {
        this.x = x;
        this.y = y;
    }
}