[SWEA] 1953번: 탈주범검거(JAVA)

SW Expert Academy

SW Expert Academy

---

• 알고리즘[접근방법]

제한 시간내에 탈주범이 갈 수 있는 경로를 다 확인(그래프의 연결성을 확인)하는 문제. 방문탐색한 곳의 개수?를 리턴.
=>BFS방법으로 구현

1) 파이프가 존재하는지
2) 흉악범이 이동할 수 있는 파이프 모양인지
3) 방문한 적 없는 곳인지를 확인해서 이동한다!

상하좌우를 메서드로 따로 뽑아서 이동할 수 있는 경로를 매번 파악한다.

---

package s0929;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class SWEA1953_탈주범검거 {
static boolean visited[][];
static int[][] map;
static int L;
static Queue<int[]> queue;
static int answer;
static void up(int r, int c, int cnt) {
    // 맵을 벗어나거나, 이미 방문했거나, 다음 진행 방향이 같지 않으면 continue;
    if (r - 1 <0 || visited[r - 1][c] == true || map[r - 1][c] == 3 || map[r - 1][c] == 4
            || map[r - 1][c] == 7 || map[r - 1][c] == 0) {
        return;
    } else {
        visited[r - 1][c] = true;
        answer++;
        queue.add(new int[] { r - 1, c, cnt + 1 });
    }
}

static void down(int r, int c, int cnt) {
    // 맵을 벗어나거나, 이미 방문했거나, 다음 진행 방향이 같지 않으면 continue;
    if (r + 1 >= map.length || visited[r + 1][c] == true || map[r + 1][c] == 3 || map[r + 1][c] == 5 || map[r + 1][c] == 6
            || map[r + 1][c] == 0) {
        return;
    } else {
        visited[r + 1][c] = true;
        answer++;
        queue.add(new int[] { r + 1, c, cnt + 1 });
    }
}

static void left(int r, int c, int cnt) {
    // 맵을 벗어나거나, 이미 방문했거나, 다음 진행 방향이 같지 않으면 continue;
    //System.out.println(r+"r"+"c-1"+(c-1));
    if (c - 1 < 0 || visited[r][c - 1] == true 
            || map[r][c - 1] == 2 || map[r][c - 1] == 6 || map[r][c - 1] == 7
            || map[r][c - 1] == 0) {
        return;
    } else {
        visited[r][c - 1] = true;
        //System.out.println("check3");
        answer++;
        queue.add(new int[] { r, c - 1, cnt + 1 });
    }
}

static void right(int r, int c, int cnt) {
    // 맵을 벗어나거나, 이미 방문했거나, 다음 진행 방향이 같지 않으면 continue;
    if (c + 1 >= map[0].length || visited[r][c + 1] == true || map[r][c + 1] == 2 || map[r][c + 1] == 4
            || map[r][c + 1] == 5 || map[r][c + 1] == 0) {
        return;
    } else {
        visited[r][c + 1] = true;
        //System.out.println("check4");
        answer++;
        queue.add(new int[] { r, c + 1, cnt + 1 });
    }
}

public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int tc = Integer.parseInt(br.readLine());
    for (int t = 1; t <= tc; t++) {
        answer = 1;
        int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 맵크기N M 맨홀위치 R C 시간 L
        map = new int[info[0]][info[1]];// 파이프가 그려진 맵
        visited = new boolean[info[0]][info[1]];// 이동한 적 있는지 확인

        int L = info[4];// 시간. 맨홀까지 가는데 1이 걸려서 빼줌
        for (int n = 0; n < map.length; n++) {
            map[n] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        // System.out.println(Arrays.deepToString(map));
        // System.out.println(L+"!!");

        queue = new LinkedList<>();
        //System.out.println(info[2] + " " + info[3]);
        queue.add(new int[] { info[2], info[3], answer }); // r,c,move,answer //dir은 map에 저장된 값
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            //System.out.println("dir" + arr[2]);
            // 남은 시간이 L과 같으면 더 확인할 필요가 없다.
            // dir체크하기
            if (arr[2] == L) {
                break;
            }
        // 이동경로확인
        switch (map[arr[0]][arr[1]]) {
        case 1:// 상하좌우
                // 상
            up(arr[0], arr[1], arr[2]);
            // 하
            down(arr[0], arr[1], arr[2]);
            // 좌
            left(arr[0], arr[1], arr[2]);
            // 우
            right(arr[0], arr[1], arr[2]);
            break;
        case 2:// 상하
                // 상
            up(arr[0], arr[1], arr[2]);
            // 하
            down(arr[0], arr[1], arr[2]);
            break;
        case 3:// 좌우
                // 좌
            left(arr[0], arr[1], arr[2]);
            // 우
            right(arr[0], arr[1], arr[2]);
            break;
        case 4:// 상우
                // 상
            up(arr[0], arr[1], arr[2]);
            // 우
            right(arr[0], arr[1], arr[2]); // 상
            break;
        case 5:// 하우
                // 하
            down(arr[0], arr[1], arr[2]);
            // 우
            right(arr[0], arr[1], arr[2]); // 하
            break;
        case 6:// 하좌
                // 하
            down(arr[0], arr[1], arr[2]);
            // 좌
            left(arr[0], arr[1], arr[2]);
            break;
        case 7:// 상좌
                // 상
            up(arr[0], arr[1], arr[2]);
            // 좌
            left(arr[0], arr[1], arr[2]);
            break;
        }
    }
        if(L!=1) {
            answer--;				
        }
        sb.append("#").append(t).append(" ").append(answer).append("\n");
    }
    System.out.println(sb);
}
}