[SWEA] 1953. [모의 SW 역량테스트] 탈주범 검거(JAVA)

:D 문제

---

교도소로 이송 중이던 흉악범이 탈출하는 사건이 발생하여 수색에 나섰다.
탈주범은 탈출한 지 한 시간 뒤, 맨홀 뚜껑을 통해 지하터널의 어느 한 지점으로 들어갔으며, 지하 터널 어딘가에서 은신 중인 것으로 추정된다. 터널끼리 연결이 되어 있는 경우 이동이 가능하므로 탈주범이 있을 수 있는 위치의 개수를 계산하여야 한다.
탈주범은 시간당 1의 거리를 움직일 수 있다. 지하 터널은 총 7 종류의 터널 구조물로 구성되어 있으며 각 구조물 별 설명은 [표 1]과 같다.

[표 1]

[그림 1-1] 은 지하 터널 지도의 한 예를 나타낸다.

이 경우 지도의 세로 크기는 5, 가로 크기는 6 이다.

맨홀 뚜껑의 위치가 ( 2, 1 ) 으로 주어질 경우, 이는 세로 위치 2, 가로 위치 1을 의미하며 [그림 1-2] 에서 붉은 색으로 표기된 구역이다.

탈주범이 탈출 한 시간 뒤 도달할 수 있는 지점은 한 곳이다.

탈주범이 2시간 후 도달할 수 있는 지점은, [그림 1-3] 과 같이 맨홀 뚜껑이 위치한 붉은 색으로 표시된 지하도 와 파란색으로 표기된 지하도까지 총 3개의 장소에 있을 수 있다.

3시간 후에는 [그림 1-4] 과 같이 총 5개의 지점에 있을 수 있다.
       

                    

 

[그림 1-1]                                                      [그림 1-2]

       

                    

[그림 1-3]                                                      [그림 1-4]

[그림 2-1] 에서 맨홀뚜껑이 위치한 지점이 ( 2, 2 ) 이고 경과한 시간이 6 으로 주어질 경우,

[그림 2-2] 에서 맨홀뚜껑이 위치한 지점은 붉은 색, 탈주범이 있을 수 있는 장소가 푸른색으로 표기되어 있다.

탈주범이 있을 수 있는 장소는, 맨홀뚜껑이 위치한 지점을 포함하여 총 15 개 이다.
       

                    

[그림 2-1]                                                      [그림 2-2]

지하 터널 지도와 맨홀 뚜껑의 위치, 경과된 시간이 주어질 때 탈주범이 위치할 수 있는 장소의 개수를 계산하는 프로그램을 작성하라.


[제약 사항]

1. 시간 제한 : 최대 50개 테이트 케이스를 모두 통과하는데, C/C++/Java 모두 1초

2. 지하 터널 지도의 세로 크기 N, 가로 크기 M은 각각 5 이상 50 이하이다. (5 ≤ N, M ≤ 50)

3. 맨홀 뚜껑의 세로 위치 R 은 0 이상 N-1이하이고 가로 위치 C 는 0 이상 M-1이하이다. (0 ≤ R ≤ N-1, 0 ≤ C ≤ M-1)

4. 탈출 후 소요된 시간 L은 1 이상 20 이하이다. (1 ≤ L ≤ 20)

5. 지하 터널 지도에는 반드시 1개 이상의 터널이 있음이 보장된다.

6. 맨홀 뚜껑은 항상 터널이 있는 위치에 존재한다.

[입력]

첫 줄에 총 테스트 케이스의 개수 T가 주어진다.

두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다.

각 테스트 케이스의 첫 줄에는 지하 터널 지도의 세로 크기 N, 가로 크기 M, 맨홀 뚜껑이 위치한장소의 세로 위치 R, 가로 위치 C, 그리고 탈출 후 소요된 시간 L 이 주어진다.

그 다음 N 줄에는 지하 터널 지도 정보가 주어지는데, 각 줄마다 M 개의 숫자가 주어진다.

숫자 1 ~ 7은 해당 위치의 터널 구조물 타입을 의미하며 숫자 0 은 터널이 없는 장소를 의미한다.

[출력]

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 기록한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 탈주범이 위치할 수 있는 장소의 개수이다.

 

SW Expert Acadmy

SW Expert Academy

 

:D 풀이 방법

---

탈주범이 위치할 수 있는 곳을 저장하기 위해 bfs 탐색을 진행하였다.  현재 맨홀 위치(R,C)를 기준으로 탐색을 시작하였다.

setDir() 메서드를 통해 현재 위치의 값을 기준으로 갈 수 있는 방향(dirs의 인덱스)를 찾아 저장하였다.

그리고 해당 정보를 가지고 bfs탐색을 진행하였다. 

먼저, 이동할 수 있는 점이 존재하는지를 확인하고, isConnected를 통해 현재 파이프와 다음으로 갈 파이프가 연결되어 있는지를 확인한다. 위 그림의 (0,0)과 (1,0)은 파이프가 연결되어 있지 않음으로 파이프가 존재해도 이동할 수 없다.

 

 

:D 작성 코드

---

package sw.expert.academy.exam1953;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution1953H {

    static class Point {
        int x, y;
        ArrayList<Integer> dirs;

        Point(int x, int y, ArrayList<Integer> dirs) {
            this.x = x;
            this.y = y;
            this.dirs = dirs;
        }
    }


    static StringBuilder answer;
    static int N, M, R, C, L;
    static int[][] map;
    static boolean[][] visited;
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상 - 하 - 좌 - 우

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        answer = new StringBuilder();
        for (int testCase = 1; testCase <= T; testCase++) {

            // 정답
            answer.append("# " + testCase + " ");

            // 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 세로 크기
            M = Integer.parseInt(st.nextToken()); // 가로 크기
            R = Integer.parseInt(st.nextToken()); // 맨홀 뚜껑 Row
            C = Integer.parseInt(st.nextToken()); // 맨홀 뚜껑 Column
            L = Integer.parseInt(st.nextToken()); // 탈출 후 경과 시간

            // map 생성 및 방문 여부 저장 배열 생성
            map = new int[N][M];
            visited = new boolean[N][M];

            // 맵 생성
            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());
                }
            }


            // 탐색 - 맨홀 위치를 기준으로
            visited[R][C] = true;
            bfs(new Point(R, C, setDir(R, C)));

        }

        System.out.print(answer.toString().trim());
    }

    // 탐색 방향 찾기
    private static ArrayList<Integer> setDir(int x, int y) {

        // 현재 지점 방향 저장
        int currentDir = map[x][y];
        ArrayList<Integer> dirs = new ArrayList<>();

        switch (currentDir) {
            case 1: // 상 - 하 - 좌 - 우 이동
                dirs.add(0);
                dirs.add(1);
                dirs.add(2);
                dirs.add(3);
                break;
            case 2: // 상 - 하 이동
                dirs.add(0);
                dirs.add(1);
                break;
            case 3: // 좌 - 우 이동
                dirs.add(2);
                dirs.add(3);
                break;
            case 4: // 상 - 우 이동
                dirs.add(0);
                dirs.add(3);
                break;
            case 5: // 우 - 하
                dirs.add(3);
                dirs.add(1);
                break;
            case 6: // 좌 - 하 이동
                dirs.add(2);
                dirs.add(1);
                break;
            case 7: // 상 - 좌 이동
                dirs.add(0);
                dirs.add(2);
                break;
            default:
                break;
        }
        return dirs;
    }

    // 해당 방향으로 탐색
    private static void bfs(Point point) {

        int cnt = 1;
        Queue<Point> queue = new ArrayDeque<>();
        Queue<Point> tmp = new ArrayDeque<>(); // queue 요소에서 갈 수 있는 점 저장
        queue.add(point);

        while (L > 1) {

            while (!queue.isEmpty()) {

                Point current = queue.poll();

                for (int idx : current.dirs) {

                    int nx = current.x + dirs[idx][0];
                    int ny = current.y + dirs[idx][1];

                    // 갈 수 있는지 확인
                    if (!isIn(nx, ny) || map[nx][ny] == 0 || visited[nx][ny]) continue;
                    Point next = new Point(nx, ny, setDir(nx, ny));

                    // 다음 파이프와 연결여부 확인
                    if (!isConnected(idx, next)) continue;

                    // 저장
                    tmp.add(next);
                    visited[nx][ny] = true;
                    cnt++;
                }
            }

            queue.addAll(tmp);
            tmp.clear();
            L--;
        }
        answer.append(cnt + "\n");
    }

    // 현재 파이프와 이동할 파이프가 연결되어 있는지 확인
    private static boolean isConnected(int idx, Point next) {

        // 홀수번(1,3)이면 -1과 연결되어야 함
        if (idx % 2 == 1) {
            if (next.dirs.contains(idx - 1)) {
                return true;
            }
        } else {
            if (next.dirs.contains(idx + 1)) {
                return true;
            }
        }
        return false;
    }

    // 범위 확인
    private static boolean isIn(int nx, int ny) {
        return nx >= 0 && ny >= 0 && nx < N && ny < M;
    }
}