SWEA1953_[모의 SW 역량테스트] 탈주범 검거

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

문제정리

1. 탈주범은 시간당 1의 거리를 움직일 수 있다.

2. 탈주범이 탈출 한 시간 뒤 도달할 수 있는 지점은 한 곳이다. 초기에 주어지는 맨홀뚜껑 위치

3. 탈주범이 있을 수 있는 곳은 처음위치도 다 포함

4. 지하 터널 지도와 맨홀 뚜껑의 위치, 경과된 시간이 주어질 때

탈주범이 위치할 수 있는 장소의 개수를 계산하는 프로그램을 작성하라.

문제issue

1. 현재위치의 터널에서 다음위치로 이동할때 가능한 터널이 자기자신이 가능한

경우도 있다.

해결흐름

1. 각 터널별로 움직이는 방향을 3차원 배열로 만들어준다.

{ {}, { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } }, // 위, 오른쪽, 아래, 왼쪽

{ { -1, 1 }, { 0, 0 } }, // 위, 아래

{ { 0, 0 }, { 1, -1 } }, // 오른쪽, 왼쪽

{ { -1, 0 }, { 0, 1 } }, // 위, 오른쪽

{ { 1, 0 }, { 0, 1 } }, // 아래, 오른쪽

{ { 1, 0 }, { 0, -1 } }, // 아래, 왼쪽

{ { -1, 0 }, { 0, -1 } } // 위, 왼쪽

};

2. 현재위치의 터널에서 다음위치로 가기 위한 조건은 범위안 , visited = false , 0이 아님

이렇게 3가지는 공통 조건이고 1번 터널의 경우 위로 움직인다면 다음위치에 있는 터널이

1,2,5,6번 터널만 가능하다. 이런식으로 각각의 터널에 조건을 달아준다.

3. 주어진 시간동안 돌면서 큐의 크기만큼 돌때 cnt++을 해줘서 이동가능한 장소를 카운트

해준다.

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
 
    static class pair {
        int n;
        int m;
 
        public pair(int n, int m) {
            super();
            this.n = n;
            this.m = m;
        }
    }
 
    private static int N;
    private static int M;
    private static int R;
    private static int C;
    private static int L;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][][] d_dir = { {}, { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } }, // 위, 오른쪽, 아래, 왼쪽
            { { -1, 1 }, { 0, 0 } }, // 위, 아래
            { { 0, 0 }, { 1, -1 } }, // 오른쪽, 왼쪽
            { { -1, 0 }, { 0, 1 } }, // 위, 오른쪽
            { { 1, 0 }, { 0, 1 } }, // 아래, 오른쪽
            { { 1, 0 }, { 0, -1 } }, // 아래, 왼쪽
            { { -1, 0 }, { 0, -1 } } // 위, 왼쪽
    };
    private static int cnt;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= test_case; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            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];
            visited = new boolean[N][M];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine().trim());
                for (int j = 0; j < M; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            bfs();
            System.out.println("#" + tc + " " + cnt);
        } // end of tc
    } // end of main
 
    private static void bfs() {
        Queue<pair> q = new LinkedList<pair>();
        q.add(new pair(R, C));
        visited[R][C] = true;
        cnt = 0;
        for (int i = 0; i < L; i++) {
            int q_size = q.size();
//                System.out.println("=========================");
            for (int j = 0; j < q_size; j++) {
                cnt++;
                pair p = q.poll();
                int n = p.n;
                int m = p.m;
//                    System.out.println("n : " + n + " m : " + m);
//                    System.out.println("map : " + map[n][m] + " length : " + d_dir[map[n][m]][0].length);
                for (int k = 0; k < d_dir[map[n][m]][0].length; k++) {
                    int nn = n + d_dir[map[n][m]][0][k];
                    int nm = m + d_dir[map[n][m]][1][k];
                    if (nn >= 0 && nn < N && nm >= 0 && nm < M && !visited[nn][nm] && map[nn][nm] != 0) {
                        if (map[n][m] == 1) {
                            if (k == 0) {
                                if (map[nn][nm] == 2 || map[nn][nm] == 5 || map[nn][nm] == 6 || map[nn][nm] == 1) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            } else if (k == 1) {
                                if (map[nn][nm] == 3 || map[nn][nm] == 6 || map[nn][nm] == 7 || map[nn][nm] == 1) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            } else if (k == 2) {
                                if (map[nn][nm] == 2 || map[nn][nm] == 4 || map[nn][nm] == 7 || map[nn][nm] == 1) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            } else if (k == 3) {
                                if (map[nn][nm] == 3 || map[nn][nm] == 4 || map[nn][nm] == 5 || map[nn][nm] == 1) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            }
                        } else if (map[n][m] == 2) {
                            if (k == 0) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 5 || map[nn][nm] == 6 || map[nn][nm] == 2) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            } else if (k == 1) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 4 || map[nn][nm] == 7 || map[nn][nm] == 2) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            }
                        } else if (map[n][m] == 3) {
                            if (k == 0) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 6 || map[nn][nm] == 7 || map[nn][nm] == 3) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            } else if (k == 1) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 4 || map[nn][nm] == 5 || map[nn][nm] == 3) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            }
                        } else if (map[n][m] == 4) {
                            if (k == 0) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 2 || map[nn][nm] == 5 || map[nn][nm] == 6) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            } else if (k == 1) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 3 || map[nn][nm] == 6 || map[nn][nm] == 7) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            }
                        } else if (map[n][m] == 5) {
                            if (k == 0) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 2 || map[nn][nm] == 4 || map[nn][nm] == 7) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            } else if (k == 1) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 3 || map[nn][nm] == 6 || map[nn][nm] == 7) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            }
                        } else if (map[n][m] == 6) {
                            if (k == 0) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 2 || map[nn][nm] == 4 || map[nn][nm] == 7) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            } else if (k == 1) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 3 || map[nn][nm] == 4 || map[nn][nm] == 5) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            }
                        } else if (map[n][m] == 7) {
                            if (k == 0) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 2 || map[nn][nm] == 5 || map[nn][nm] == 6) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            } else if (k == 1) {
                                if (map[nn][nm] == 1 || map[nn][nm] == 3 || map[nn][nm] == 4 || map[nn][nm] == 5) {
                                    q.add(new pair(nn, nm));
                                    visited[nn][nm] = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    } // end of bfs
} // end of class