SWEA 모의 1963 탈주범 검거

SWEA 모의 1963 탈주범 검거

 

 

문제링크

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

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

고려사항

* 파이프 정보
  - 파이프는 1~7까지 고정된 형태로 주어지며 들어가는 구멍과 나가는 구멍이 중요
  - boolean[][] 형태에 열린 공간은 true로 설정
  - 이때 방향은 북쪽을 0으로 해서 시계방향으로 맞춰야 나중에 사방탐색 할 때나 파이프간의 연결을 확인할 때 수월하다.
 

* 탐색
  - 가장 기본적으로는 맨홀의 위치에서 사방 탐색으로 주어진 시간 동안 방문할 수 있는 모든 지점들의 개수를 출력하는 문제
  - 사방 탐색 과정에서 4 방향을 모두 갈 수 있는 것이 아니라 파이프의 타입에 따라서 갈수 있는 지점이 한정된다.
  - 또한 이동할 수 있다고 하더라고 다음 지점에서 탈주범을 받아줄 수 있어야 한다.
  - 다음 지점에 탈주범이 도달하려면 현재 파이프와 다음 파이프가 연결되어야 하는데
  - 이를 쉽게 하기 위해 북쪽(0)번에서 시계방향으로 방향을 정해서
  - 1, 3번과 0, 2번이 짝이 된다면 (내꺼+2)/4를 하면 상대편꺼가 나옴 1의 상대는 -> 3, 4의 상대는 2
  - 또한 주어진 시간을 넘어가면 탐색을 종료해줘야 함

 * 시간의 측정
  - 한번의 BFS 탐색에 한 시간이 소요되며 최대 L 시간까지 도망갈 수 있음
  - 최초 시간은 1에서 시작하는 것도 혼돈의 함정

입력사항

 * 지하 터널 지도의 세로 크기 N, 가로 크기 M은 각각 5 이상 50 이하이다.
 * 맨홀 뚜껑의 위치 R, C는 지도의 영역 내부에 존재한다. 또한 맨홀은 언제나 터널 위에 존재한다.
 * 탈출 후 소요된 시간 L은 1 이상 20 이하이다. -- 처음 시작 시간이 1이라는 점을 주의 한다.
 * 지하 터널 지도에는 반드시 1개 이상의 터널이 있음이 보장된다.
 * 터널 구조물의 타입은 총 7개로 0인 지점은 애초에 터널이 없어서 갈 수 없는 지점이다.

출력사항

 * 탈주범이 위치할 수 있는 장소의 개수
  - 탈주범은 탈주범이 지나온 길 어디에나 있을 수 있다. 즉 방문했던 지점의 개수가 필요

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

 

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.모의;

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

public class SWEA_모의_1963_탈주범검거 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens = null;

    static int TC;
    static int N;// 세로 크기
    static int M;// 가로 크기
    static int R;// 맨홀의 세로 위치
    static int C;// 맨홀의 가로 위치
    static int L;// 탈출한 후 소요된 시간

    static int[][] map;
    static int answer;
    static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    static boolean[][] pipes = {{},
            {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 IOException {
        input = new BufferedReader(new StringReader(src));
        TC = Integer.parseInt(input.readLine());

        for (int t = 1; t <= TC; t++) {
            tokens = new StringTokenizer(input.readLine());
            N = Integer.parseInt(tokens.nextToken());
            M = Integer.parseInt(tokens.nextToken());
            R = Integer.parseInt(tokens.nextToken());
            C = Integer.parseInt(tokens.nextToken());
            L = Integer.parseInt(tokens.nextToken());

            map = new int[N][M];
            for (int r = 0; r < N; r++) {
                tokens = new StringTokenizer(input.readLine(), " ");
                for (int c = 0; c < M; c++) {
                    map[r][c] = Integer.parseInt(tokens.nextToken());
                }
            }
            answer = 0;

            bfs();

            output.append("#").append(t).append(" ").append(answer).append("\n");
        }
        System.out.println(output);
    }

    static void bfs() {
        Point start = new Point(R, C, 1);
        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        visited[start.row][start.col] = true;
        q.offer(start);

        while (!q.isEmpty()) {
            Point front = q.poll();
            if (front.depth > L) {
                return;
            }
            answer++;

            for (int d = 0; d < dirs.length; d++) {
                // 해당 방향의 이동이 가능한가?
                if (pipes[front.ptype][d]) {
                    int nr = front.row + dirs[d][0];
                    int nc = front.col + dirs[d][1];

                    // 안에 있고 미방문이고 파이프라면 이동가능
                    if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] > 0) {
                        // 해당 방향에 도착할 수 있는가?
                        int nt = map[nr][nc];
                        if (pipes[nt][(d + 2) % 4]) {
                            visited[nr][nc] = true;
                            q.offer(new Point(nr, nc, front.depth + 1));
                        }
                    }
                }
            }
        }
    }

    static boolean isIn(int row, int col) {
        return 0 <= row && row < N && 0 <= col && col < M;
    }

    static class Point {
        int row, col;
        int depth;// 이동 시간과 유관
        int ptype;// 해당 지점의 파이프 타입

        public Point(int row, int col, int depth) {
            this.row = row;
            this.col = col;
            this.depth = depth;
            ptype = map[row][col];
        }

        @Override
        public String toString() {
            return "[(" + row + "," + col + ", d=" + depth + ", t=" + ptype + "]";
        }
    }

    static String src = "5\r\n" +
                        "5 6 2 1 3\r\n" +
                        "0 0 5 3 6 0\r\n" +
                        "0 0 2 0 2 0\r\n" +
                        "3 3 1 3 7 0\r\n" +
                        "0 0 0 0 0 0\r\n" +
                        "0 0 0 0 0 0\r\n" +
                        "5 6 2 2 6\r\n" +
                        "3 0 0 0 0 3\r\n" +
                        "2 0 0 0 0 6\r\n" +
                        "1 3 1 1 3 1\r\n" +
                        "2 0 2 0 0 2\r\n" +
                        "0 0 4 3 1 1\r\n" +
                        "10 10 4 3 9\r\n" +
                        "0 0 0 0 0 0 0 0 0 0\r\n" +
                        "0 0 0 7 5 0 5 0 0 0\r\n" +
                        "0 0 3 2 2 6 0 0 0 0\r\n" +
                        "0 4 7 2 2 2 7 0 0 4\r\n" +
                        "0 3 0 1 1 2 2 0 0 5\r\n" +
                        "0 5 6 1 1 1 1 6 2 5\r\n" +
                        "7 4 1 2 0 0 4 6 0 0\r\n" +
                        "5 3 1 7 0 2 2 6 5 7\r\n" +
                        "7 3 2 1 1 7 1 0 2 7\r\n" +
                        "3 4 0 0 4 0 5 1 0 1\r\n" +
                        "20 20 13 11 13\r\n" +
                        "0 0 0 1 4 4 4 0 0 0 0 0 0 0 0 1 2 3 1 0\r\n" +
                        "0 0 0 0 0 0 0 0 0 0 0 4 2 7 7 2 0 1 1 0\r\n" +
                        "0 0 0 0 0 0 0 0 0 6 2 4 4 2 0 4 7 0 6 0\r\n" +
                        "0 0 0 7 5 5 3 0 0 7 5 0 5 6 4 2 6 3 1 5\r\n" +
                        "0 0 0 1 2 6 3 3 7 0 3 6 2 4 5 6 7 7 5 7\r\n" +
                        "0 0 0 3 7 6 1 5 3 3 4 5 7 6 0 4 3 3 1 1\r\n" +
                        "0 1 2 1 5 6 1 6 1 6 5 1 6 0 0 3 4 1 7 6\r\n" +
                        "0 2 3 2 2 7 3 0 0 3 2 5 2 1 0 6 5 1 6 5\r\n" +
                        "0 2 5 7 0 7 1 3 3 4 1 3 3 0 2 3 3 2 4 1\r\n" +
                        "4 0 0 7 2 4 2 2 1 3 1 6 5 5 6 2 5 1 1 6\r\n" +
                        "5 6 4 0 3 6 5 2 2 6 1 2 0 1 7 5 7 2 2 2\r\n" +
                        "1 6 3 1 4 4 1 0 3 0 4 2 7 2 0 2 3 6 2 5\r\n" +
                        "1 5 7 2 1 1 4 4 2 1 0 2 7 1 6 2 6 6 2 2\r\n" +
                        "3 7 0 6 5 0 4 0 6 6 7 1 3 1 1 1 5 1 6 6\r\n" +
                        "0 4 0 1 6 2 1 0 7 0 4 2 5 2 7 0 2 7 1 6\r\n" +
                        "0 7 3 0 1 7 6 2 0 0 4 2 4 1 3 3 7 0 1 3\r\n" +
                        "0 1 1 4 3 7 4 5 2 2 4 7 4 7 7 4 6 0 1 6\r\n" +
                        "0 5 2 2 1 4 6 3 7 0 6 3 5 0 0 6 4 4 2 1\r\n" +
                        "0 1 2 4 5 6 0 2 0 0 5 6 2 4 6 4 7 6 3 7\r\n" +
                        "7 7 4 2 3 0 0 4 0 0 7 2 7 5 6 1 4 5 5 4\r\n" +
                        "50 50 20 12 18\r\n" +
                        "0 0 0 0 0 0 0 0 0 0 0 0 4 5 0 0 0 0 0 4 2 0 5 2 1 5 3 3 0 0 4 0 5 1 7 2 6 0 7 0 0 0 2 0 0 0 0 0 0 0\r\n" +
                        "6 7 0 0 0 0 0 0 0 0 0 0 4 5 5 3 6 3 0 2 3 3 0 0 5 6 1 5 3 4 7 6 2 2 1 1 6 5 6 4 6 2 0 0 0 0 2 3 1 0\r\n" +
                        "0 2 6 5 7 6 0 0 0 0 0 0 6 2 0 5 6 2 0 4 1 5 0 0 2 0 7 7 0 6 0 6 2 2 4 1 2 2 1 6 6 6 0 2 2 5 0 6 5 0\r\n" +
                        "0 0 0 4 7 2 7 3 7 0 0 0 0 6 7 6 5 1 1 1 2 2 1 3 1 2 7 6 1 2 1 2 4 1 6 1 1 7 3 1 6 6 6 1 1 1 7 0 0 0\r\n" +
                        "0 0 0 5 4 0 6 3 3 7 0 0 0 6 4 3 2 5 3 1 6 1 0 4 1 0 5 7 6 3 1 1 3 6 1 1 6 3 6 7 3 3 6 5 0 7 2 2 4 6\r\n" +
                        "0 6 0 7 6 0 7 4 0 5 3 0 4 3 2 0 5 7 3 0 1 3 6 7 7 5 1 7 5 2 0 5 3 1 3 7 1 1 1 5 2 5 1 3 6 7 7 6 4 3\r\n" +
                        "5 2 0 2 6 5 0 5 6 1 6 5 5 1 7 1 2 3 6 5 1 6 7 7 6 4 1 7 5 2 0 1 3 4 6 4 5 7 2 6 5 6 2 5 6 5 6 5 1 6\r\n" +
                        "1 2 0 7 0 5 5 0 7 6 2 2 1 3 5 5 3 6 3 7 6 4 1 3 1 3 7 0 3 7 0 2 5 6 1 3 4 1 5 1 7 4 1 7 7 0 4 7 5 5\r\n" +
                        "7 6 0 3 5 1 4 0 5 2 5 0 1 3 5 5 4 4 6 1 6 5 7 6 2 1 6 5 5 3 0 5 7 1 1 3 6 2 2 2 4 5 7 4 5 1 1 0 7 3\r\n" +
                        "2 5 4 0 3 1 4 5 6 3 7 0 4 5 3 6 4 5 1 7 4 7 3 1 1 7 7 1 1 5 6 4 7 1 2 6 4 1 7 2 7 1 6 0 5 0 0 0 1 0\r\n" +
                        "3 0 2 5 1 7 1 1 1 6 5 1 3 1 3 1 1 7 1 3 6 5 5 3 1 3 1 6 2 3 2 6 6 1 1 7 5 7 5 7 1 6 0 3 5 1 5 3 0 0\r\n" +
                        "0 0 3 2 0 1 4 1 4 1 0 7 3 2 2 4 2 4 4 6 1 1 1 7 2 4 7 4 3 6 3 5 1 6 1 3 7 7 2 6 3 2 1 0 4 6 2 6 3 0\r\n" +
                        "0 0 5 4 7 2 4 6 4 1 6 7 2 2 1 6 2 1 5 4 7 2 2 1 0 7 6 1 7 2 5 7 0 4 1 6 4 0 3 0 0 5 5 0 7 7 0 3 0 0\r\n" +
                        "0 0 6 4 3 1 3 1 4 7 2 1 2 4 3 4 1 6 2 1 5 1 1 6 0 7 2 7 2 4 7 4 0 3 7 7 3 3 5 2 0 4 3 0 4 2 0 1 3 5\r\n" +
                        "0 1 0 5 6 4 4 6 5 7 0 6 1 4 5 6 2 1 2 4 4 1 1 2 6 1 6 2 0 3 7 3 0 0 5 1 7 6 6 6 1 3 4 2 1 0 7 0 5 5\r\n" +
                        "0 7 2 1 4 2 7 3 0 2 1 4 3 5 1 1 1 1 7 1 4 4 1 7 6 0 1 2 0 5 2 0 0 0 5 4 0 3 7 5 3 1 4 1 2 7 2 6 6 4\r\n" +
                        "0 1 3 0 3 4 6 3 4 2 4 0 7 5 1 1 2 7 1 6 4 2 2 0 5 6 3 3 1 1 0 0 0 3 0 4 5 4 3 1 1 6 1 6 2 0 1 4 7 7\r\n" +
                        "0 3 0 0 2 6 1 4 7 5 1 4 3 2 5 1 4 3 6 3 0 2 4 5 7 5 6 2 0 5 6 3 6 4 6 2 0 0 6 0 7 2 2 6 0 0 0 0 0 0\r\n" +
                        "0 6 7 1 6 4 3 6 0 2 6 7 6 2 1 6 6 6 2 0 0 7 3 0 1 1 2 0 0 0 3 1 6 7 5 6 4 1 7 5 2 0 2 6 0 0 0 0 4 0\r\n" +
                        "0 6 7 7 3 3 0 2 0 1 6 4 1 1 1 6 2 3 3 4 2 3 5 0 5 7 7 6 2 7 2 7 3 1 0 5 6 7 1 6 4 1 5 0 0 0 0 0 0 0\r\n" +
                        "0 7 3 0 4 3 0 0 6 6 0 5 1 1 1 1 1 6 0 0 7 0 0 0 2 4 3 2 3 3 6 0 0 1 0 2 6 7 3 4 0 3 2 4 0 0 0 0 0 7\r\n" +
                        "0 0 4 7 2 0 0 0 1 4 2 4 7 7 2 4 2 4 0 5 6 0 0 0 7 0 2 7 4 4 1 6 1 4 2 3 6 2 0 6 5 3 5 0 3 5 6 0 0 1\r\n" +
                        "0 0 7 4 7 0 3 0 4 4 6 2 4 7 0 5 7 1 3 6 5 6 6 7 3 3 6 6 4 2 0 0 3 0 4 7 2 6 4 0 6 2 4 6 7 1 7 2 7 1\r\n" +
                        "0 0 2 6 0 0 6 5 0 4 1 2 2 2 2 7 2 1 0 4 6 4 1 0 1 1 2 2 0 4 4 2 0 0 3 0 3 6 2 2 7 6 6 0 4 6 0 2 2 2\r\n" +
                        "0 0 4 4 7 1 1 1 7 3 7 6 2 3 3 0 5 0 0 6 1 2 6 3 1 7 0 4 7 4 3 6 1 5 1 0 3 7 4 0 3 0 5 6 2 0 0 3 0 5\r\n" +
                        "0 0 7 3 0 5 4 0 7 4 0 0 4 5 7 1 3 2 3 3 5 3 5 3 5 5 5 5 4 2 3 6 0 3 1 7 2 4 5 3 0 0 5 3 6 0 0 7 3 6\r\n" +
                        "0 0 3 5 0 0 1 1 1 0 0 0 5 3 5 5 1 2 7 0 4 3 1 6 7 1 5 7 4 4 5 7 0 3 6 3 3 7 7 4 1 3 5 2 0 0 0 7 7 4\r\n" +
                        "0 0 7 6 3 5 0 7 2 7 7 5 4 0 0 7 0 4 0 0 3 2 3 1 5 7 4 6 0 3 5 5 2 0 6 0 0 0 2 1 1 4 3 6 2 0 5 1 1 6\r\n" +
                        "0 0 1 0 4 1 0 2 5 0 0 0 6 7 3 7 0 0 0 0 4 3 3 3 0 1 0 0 0 1 5 1 5 4 5 1 7 0 0 5 0 5 6 0 3 2 5 0 3 4\r\n" +
                        "0 0 0 0 0 4 0 2 3 1 6 6 6 3 5 3 6 0 0 0 4 7 0 6 1 7 1 0 0 5 5 2 5 1 0 1 1 3 3 4 1 4 2 0 6 3 0 0 6 4\r\n" +
                        "6 4 2 2 0 0 0 3 3 0 0 1 4 0 5 0 2 0 7 0 1 7 7 1 5 7 0 0 0 3 1 5 5 6 0 6 2 6 4 0 7 6 5 1 3 3 7 0 2 5\r\n" +
                        "0 0 0 7 7 0 0 4 4 3 1 6 1 0 1 3 3 1 4 5 7 3 7 0 0 4 0 0 0 7 3 7 2 2 0 1 5 0 7 5 5 2 5 1 0 2 0 0 3 2\r\n" +
                        "0 0 0 3 0 0 0 0 1 2 6 7 1 6 7 0 3 5 2 7 3 0 4 5 2 0 0 0 0 2 5 7 3 7 5 6 0 0 2 2 5 4 7 6 4 5 1 4 4 6\r\n" +
                        "0 4 3 0 0 0 0 3 5 6 3 2 0 3 6 0 6 0 0 1 4 3 6 2 4 7 4 7 1 5 0 4 0 0 2 0 0 0 3 7 6 1 2 5 3 5 2 3 3 3\r\n" +
                        "0 0 0 1 4 0 0 2 1 0 2 0 0 1 7 3 4 3 3 4 7 0 6 7 4 7 3 1 6 1 7 3 4 4 7 5 2 1 3 7 2 5 2 3 3 2 3 0 1 2\r\n" +
                        "0 0 0 0 1 1 0 0 5 7 3 6 6 0 0 6 5 4 2 7 0 0 4 5 5 0 5 7 3 3 0 3 5 5 3 6 0 0 3 5 4 0 0 7 5 1 6 0 0 7\r\n" +
                        "0 0 0 0 5 6 3 1 5 2 0 7 7 7 0 0 1 0 3 6 4 1 6 7 2 1 6 5 2 0 0 7 4 5 0 0 0 0 0 6 6 0 0 5 6 0 2 3 4 5\r\n" +
                        "0 0 7 1 0 1 6 5 6 0 0 5 4 5 7 1 1 6 5 2 2 0 3 7 4 5 2 6 4 0 0 3 4 0 0 0 0 0 0 7 7 7 7 6 4 3 4 4 0 0\r\n" +
                        "0 0 0 1 3 0 0 3 7 1 1 0 4 1 4 4 2 6 1 6 2 2 7 4 2 4 1 7 1 6 4 3 3 1 3 4 0 0 3 2 0 2 0 1 3 3 4 7 1 5\r\n" +
                        "0 0 0 3 4 0 0 2 0 5 5 0 0 1 4 4 0 4 0 1 6 6 4 2 1 0 0 3 7 0 4 3 3 2 3 5 3 5 0 4 0 5 0 3 0 7 7 3 5 6\r\n" +
                        "0 0 0 7 2 0 0 4 2 2 6 2 2 5 0 5 0 3 4 3 5 5 2 0 4 0 0 5 0 0 4 1 6 4 4 3 4 0 0 5 0 1 1 2 0 7 3 4 0 4\r\n" +
                        "0 0 1 1 4 4 1 0 0 0 3 5 4 5 4 2 7 4 6 1 6 7 0 3 0 7 1 7 6 6 3 0 5 7 6 6 4 7 3 4 5 0 0 0 0 6 1 1 5 3\r\n" +
                        "0 0 4 2 5 7 4 4 2 1 2 1 3 4 7 2 7 2 1 6 3 3 0 7 5 6 6 4 5 5 3 3 2 7 5 3 1 4 7 0 0 0 0 0 0 3 1 5 6 5\r\n" +
                        "0 0 0 4 4 1 0 0 6 0 0 7 5 7 5 1 7 3 6 0 2 4 3 4 7 7 3 0 0 0 1 5 5 0 6 7 7 7 4 4 3 6 3 7 5 0 1 1 0 2\r\n" +
                        "0 0 0 1 3 4 7 2 5 0 0 4 4 0 5 2 2 0 1 7 0 1 1 3 6 5 2 6 2 7 7 3 6 7 1 3 4 6 7 5 3 7 4 6 0 0 0 4 3 1\r\n" +
                        "0 0 0 2 1 6 3 5 4 0 0 6 0 0 6 7 0 0 5 2 0 7 7 0 7 0 0 7 7 6 0 0 1 1 0 1 0 1 3 1 0 0 4 7 7 0 0 0 2 6\r\n" +
                        "0 0 0 2 4 0 6 7 2 4 1 5 6 3 0 0 0 0 4 2 7 1 1 5 2 0 0 7 2 2 3 1 3 5 5 7 7 4 0 3 4 2 3 0 0 4 6 6 0 1\r\n" +
                        "0 0 0 4 6 1 0 3 6 4 7 3 5 0 0 0 0 0 0 7 0 0 3 6 2 1 0 2 3 4 6 7 5 0 7 0 5 4 5 1 5 0 0 0 0 4 5 3 1 0\r\n" +
                        "1 3 6 5 5 2 3 7 6 1 0 6 7 3 2 5 6 7 6 6 0 0 7 1 0 5 5 0 3 0 2 0 7 4 5 3 2 5 1 5 3 0 0 0 1 2 0 1 0 0\r\n" +
                        "1 7 3 0 2 0 7 0 4 6 1 1 5 0 7 0 5 7 7 2 6 0 0 1 0 2 3 3 4 2 7 5 3 7 0 0 4 6 6 6 3 0 0 0 7 7 7 5 7 2";
}