[SWEA] 1953번 : 탈주범 검거

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

 

문제

 

입력

 

출력

 

 

---

소스코드

DFS 사용

import java.io.*;
import java.util.*;

class Solution {
    static int arr[][];
    static int n, m, r, c, l;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            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());

            arr = new int[n][m];
            visited = new boolean[n][m];
            mark = new boolean[n][m];
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < m; k++) {
                    arr[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            result = 0;
            dfs(r,c,1);
            for (int j = 0; j <n; j++) {
                for (int k = 0; k < m; k++) {
                    if(mark[j][k]) result++;
                }
            }

            sb.append("#" + (i + 1) + " " + result + "\n");
        }
        System.out.println(sb);
    }

    // 상, 우, 하, 좌
    static int rx[] = {-1, 0, 1, 0};
    static int ry[] = {0, 1, 0, -1};
    static boolean visited[][];
    static boolean mark[][];
    static int result;
    static final int[][] typeTunnel = {	// 터널 종류별로 4방향에 대해 뚫려 있는지 여부
            {0, 0, 0, 0},
            {1, 1, 1, 1},	// 모든 방향 가능
            {1, 0, 1, 0},
            {0, 1, 0, 1},
            {1, 1, 0, 0},
            {0, 1, 1, 0},
            {0, 0, 1, 1},
            {1, 0, 0, 1},
    };

    static void dfs(int x, int y, int time) {
        mark[x][y] = true;
        if(time == l) return;

        int[] dirs = typeTunnel[arr[x][y]];
        for (int i = 0; i < dirs.length; i++) {
            if (dirs[i] == 0) continue;

            int nx = x + rx[i];
            int ny = y + ry[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(visited[nx][ny]) continue;
            if(arr[nx][ny] == 0) continue;

            if (typeTunnel[arr[nx][ny]][(i + 2) % 4] == 1) { // 다음 칸에서 터널이 이어지는 경우에만 진행
                visited[nx][ny] = true;
                dfs(nx, ny, time + 1);
                visited[nx][ny] = false; // 백트래킹
            }
        }
    }
}

 

BFS 사용

import java.io.*;
import java.util.*;

class Solution {
    static int arr[][];
    static int n, m, r, c, l;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            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());

            arr = new int[n][m];
            visited = new boolean[n][m];
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < m; k++) {
                    arr[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            result = 0;
            bfs(r, c);

            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (visited[j][k]) result++;
                }
            }

            sb.append("#" + (i + 1) + " " + result + "\n");
        }
        System.out.println(sb);
    }

    // 상, 우, 하, 좌
    static int rx[] = {-1, 0, 1, 0};
    static int ry[] = {0, 1, 0, -1};
    static boolean visited[][];
    static int result;
    static final int[][] typeTunnel = {    // 터널 종류별로 4방향에 대해 뚫려 있는지 여부(상, 우, 하, 좌)
            {0, 0, 0, 0},
            {1, 1, 1, 1},    // 모든 방향 가능
            {1, 0, 1, 0},
            {0, 1, 0, 1},
            {1, 1, 0, 0},
            {0, 1, 1, 0},
            {0, 0, 1, 1},
            {1, 0, 0, 1},
    };

    static void bfs(int x, int y) {
        Deque<int[]> q = new ArrayDeque<>();
        q.addLast(new int[]{x, y});
        visited[x][y] = true;

        int time = 0;
        while (!q.isEmpty()) {
            time++;
            if (time == l) break;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] now = q.pollFirst();
                int[] dir = typeTunnel[arr[now[0]][now[1]]];
                for (int j = 0; j < 4; j++) {
                    if (dir[j] == 0) continue;

                    int nx = now[0] + rx[j];
                    int ny = now[1] + ry[j];

                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if (arr[nx][ny] == 0 || visited[nx][ny]) continue;

                    if (typeTunnel[arr[nx][ny]][(j + 2) % 4] == 1) {
                        visited[nx][ny] = true;
                        q.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

 

해결 방법

1. DFS, BFS 중 하나를 사용해야 한다. 본인은 DFS를 사용하였으나 BFS가 더 맞는 문제이다.
2. 맨홀 뚜껑이 위치한 지점에서 DFS 탐색을 시작한다.
3. 각 터널마다 이동가능한 상, 우, 하, 좌를 나타내기 위해 typeTunnel를 두었다..
4. typeTunnel로는 "각 터널이 갈 수 있는 위치"와 "다음 칸의 터널과 현재 터널이 연결되어 있는지" 판별할 수 있다.
5. 이미 방문한 터널에 다른 경로로 다시 방문할 수 있기때문에 방문처리(visited)를 백트래킹해야 한다.
6. 방문한 터널엔 mark 표시를 한다.

 

https://velog.io/@wonthechan/SWEA-1953%EB%B2%88-%ED%83%88%EC%A3%BC%EB%B2%94-%EA%B2%80%EA%B1%B0#%EB%B0%A9%ED%96%A5-%ED%95%98%EB%93%9C%EC%BD%94%EB%94%A9