[SWEA/모의 SW 역량테스트] 1953. 탈주범 검거 - JAVA 자바

• 131ms
• BFS 구현

경우에 따라 가지처럼 뻗어나가는 구조로 BFS 를 이용하여 구현하였다.

 

탈주범의 위치와 시간을 저장할 수 있는 Node 클래스를 만들어서 맨홀의 위치(시작위치)를 Queue에 넣고 반복문을 시작해준다.

터널의 모양에 따라 갈 수 있는 방향인지, 영역 내인지, 방문한 곳인지 조건문을 통해 체크한 후 지나갈 수 있는 곳이라면 방문 체크 및 한 시간을 더하여 다시 큐에 넣어주며 반복한다.

 

지정한 시간이 되거나 더이상 이동할 경로가 없는 경우 = Queue가 빈 경우 반복문이 종료되며 탈주범이 있을 수 있는 위치를 count한 값을 출력해준다.

 

여러 조건만 잘 체크하면 쉽게 풀 수 있는 문제였다.

 

👩🏻‍💻 소스코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Solution {

    static class Node {
        int x;
        int y;
        int time;

        public Node(int x, int y, int time) {
            super();
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        int[] dx = { 0, 0, -1, 1 };
        int[] dy = { 1, -1, 0, 0 };

        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int R = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            int L = Integer.parseInt(st.nextToken()); // 흐른 시간

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

            Deque<Node> q = new ArrayDeque<>();
            q.offer(new Node(R, C, 1));
            visited[R][C] = true;
            int count = 1;
            while (!q.isEmpty()) {
                Node now = q.poll();
                if (now.time == L)
                    break;

                for (int i = 0; i < 4; i++) {

                    // 지나갈 수 없는 방향이면 continue;
                    if(board[now.x][now.y] == 2 && (i==0 || i==1) ) continue;
                    if(board[now.x][now.y] == 3 && (i==2 || i==3) ) continue;
                    if(board[now.x][now.y] == 4 && (i==1 || i==3) ) continue;
                    if(board[now.x][now.y] == 5 && (i==1 || i==2) ) continue;
                    if(board[now.x][now.y] == 6 && (i==0 || i==2) ) continue;
                    if(board[now.x][now.y] == 7 && (i==0 || i==3) ) continue;

                    int nx = now.x + dx[i];
                    int ny = now.y + dy[i];

                    // 지나갈 수 있는 방향 및 방문하지 않는 곳이면
                    if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny] && board[nx][ny] != 0) {
                        int tmp = board[nx][ny];

                        if (i == 0 && (tmp == 1 || tmp == 3 || tmp == 6 || tmp == 7)) {
                            count++;
                            visited[nx][ny] = true;
                            q.offer(new Node(nx, ny, now.time + 1));
                        } else if (i == 1 && (tmp == 1 || tmp == 3 || tmp == 4 || tmp == 5)) {
                            count++;
                            visited[nx][ny] = true;
                            q.offer(new Node(nx, ny, now.time + 1));
                        } else if (i == 2 && (tmp == 1 || tmp == 2 || tmp == 5 || tmp == 6)) {
                            count++;
                            visited[nx][ny] = true;
                            q.offer(new Node(nx, ny, now.time + 1));
                        } else if (i == 3 && (tmp == 1 || tmp == 2 || tmp == 4 || tmp == 7)) {
                            count++;
                            visited[nx][ny] = true;
                            q.offer(new Node(nx, ny, now.time + 1));
                        }

                    }

                }
            }

            sb.append('#').append(t).append(' ').append(count).append('\n');

        }
        System.out.println(sb);
    }
}