[SWEA] 탈주범 검거

[1953] 탈주범 검거

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

 

Solution

• 터널 구조에 따라 이동할 수 있는 방향과 다음 터널과의 연결여부를 체크하면서 BFS로 풀이했다.
• switch문을 더 깔끔하게 풀었으면 좋았을텐데..

 

 

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    static int tc, n, m, r, c, l, count;
    static int[][] map, visited, copy;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static int[][] search = { { 1, 2, 5, 6 }, { 1, 2, 4, 7 }, { 1, 3, 4, 5 }, { 1, 3, 6, 7 } }; // U, D, L, R
 
    static class Node {
        private int x, y;
 
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        tc = sc.nextInt();
        for (int tn = 1; tn <= tc; tn++) {
            n = sc.nextInt();
            m = sc.nextInt();
            r = sc.nextInt();
            c = sc.nextInt();
            l = sc.nextInt();
 
            map = new int[n][m];
            copy = new int[n][m];
            visited = new int[n][m];
 
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
 
            bfs(r, c);
            count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (copy[i][j] > 0 && copy[i][j] <= l) {
                        count++;
                    }
                }
            }
            System.out.println("#" + tn + " " + count);
 
        }
    }
 
    static void print(int[][] arr) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
 
    static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        visited[x][y] = 1;
        copy[x][y] = 1;
 
        while (!q.isEmpty()) {
            Node cur = q.poll();
            int nx, ny;
            switch (map[cur.x][cur.y]) {
            case 1: // [0, 1, 2, 3]
                for (int i = 0; i < 4; i++) {
                    nx = cur.x + dx[i];
                    ny = cur.y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == 0 && map[nx][ny] > 0) {
                        for (int j = 0; j < 4; j++) {
                            if (map[nx][ny] == search[i][j]) {
                                q.offer(new Node(nx, ny));
                                visited[nx][ny] = 1;
                                copy[nx][ny] = copy[cur.x][cur.y] + 1;
                            }
                        }
                    }
                }
                break;
            case 2: // [0, 1]
                for (int i = 0; i < 2; i++) {
                    nx = cur.x + dx[i];
                    ny = cur.y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == 0 && map[nx][ny] > 0) {
                        for (int j = 0; j < 4; j++) {
                            if (map[nx][ny] == search[i][j]) {
                                q.offer(new Node(nx, ny));
                                visited[nx][ny] = 1;
                                copy[nx][ny] = copy[cur.x][cur.y] + 1;
                            }
                        }
                    }
                }
                break;
            case 3: // [2, 3]
                for (int i = 2; i < 4; i++) {
                    nx = cur.x + dx[i];
                    ny = cur.y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == 0 && map[nx][ny] > 0) {
                        for (int j = 0; j < 4; j++) {
                            if (map[nx][ny] == search[i][j]) {
                                q.offer(new Node(nx, ny));
                                visited[nx][ny] = 1;
                                copy[nx][ny] = copy[cur.x][cur.y] + 1;
                            }
                        }
                    }
                }
                break;
            case 4: // [0, 3]
                for (int i = 0; i < 4; i += 3) {
                    nx = cur.x + dx[i];
                    ny = cur.y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == 0 && map[nx][ny] > 0) {
                        for (int j = 0; j < 4; j++) {
                            if (map[nx][ny] == search[i][j]) {
                                q.offer(new Node(nx, ny));
                                visited[nx][ny] = 1;
                                copy[nx][ny] = copy[cur.x][cur.y] + 1;
                            }
                        }
                    }
                }
                break;
            case 5: // [1, 3]
                for (int i = 1; i < 4; i += 2) {
                    nx = cur.x + dx[i];
                    ny = cur.y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == 0 && map[nx][ny] > 0) {
                        for (int j = 0; j < 4; j++) {
                            if (map[nx][ny] == search[i][j]) {
                                q.offer(new Node(nx, ny));
                                visited[nx][ny] = 1;
                                copy[nx][ny] = copy[cur.x][cur.y] + 1;
                            }
                        }
                    }
                }
                break;
            case 6: // [1, 2]
                for (int i = 1; i < 3; i++) {
                    nx = cur.x + dx[i];
                    ny = cur.y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == 0 && map[nx][ny] > 0) {
                        for (int j = 0; j < 4; j++) {
                            if (map[nx][ny] == search[i][j]) {
                                q.offer(new Node(nx, ny));
                                visited[nx][ny] = 1;
                                copy[nx][ny] = copy[cur.x][cur.y] + 1;
                            }
                        }
                    }
                }
                break;
            case 7: // [0, 2]
                for (int i = 0; i < 3; i += 2) {
                    nx = cur.x + dx[i];
                    ny = cur.y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == 0 && map[nx][ny] > 0) {
                        for (int j = 0; j < 4; j++) {
                            if (map[nx][ny] == search[i][j]) {
                                q.offer(new Node(nx, ny));
                                visited[nx][ny] = 1;
                                copy[nx][ny] = copy[cur.x][cur.y] + 1;
                            }
                        }
                    }
                }
                break;
            }
        }
    }
}