<Algorithm> 155. 탈주범검거(SWExpert)

1. 탈주범검거(SWExpert)

   사용 알고리즘 :  BFS

• 문제를 슬쩍보고 에이 간단한 BFS 문제네 하고 풀었는데 호되게 혼났다...

• 문제의 조건들을 확실하게 봐야한다는 교훈을 얻었다. 이문제는 통로가 연결되는 통로인지 아닌지가 중요하다..

문제에 대한 접근&생각

1. 통로를 시간에 맞춰 탐색 -> BFS!
2. 통로가 없는 경우는 0이다, 통로는 연결되어있어야한다. -> 탐색안하는 조건!
3. 통로는 7가지가 있고 각각 방향이 다르다 -> 탐색하는 방향!
4. 최초 통로도 포함된다 -> 초기값설정!
5. 탐색하는 시간이 주어진다 -> 종료조건!

다른 방법 풀이

• DFS로 해당시간까지 탐색한다.  

• 제일 짧은 코드에서 갈수있는 방향 체크를 하,우,상,좌로 두고 (i+2)%4로 체크하고 나처럼 3차원배열이 아닌 2,1차원을 따로 분리했다.

내 코드 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
 
public class Solution {
    static int n,m,l;
    static int[][] map;
    static List<Integer>[] dirlist;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int t = 1; t <= T; t++) {
            /******************************
             * BFS를 이용해서 갈수 있는 방향에 대한
             * 탐색을 진행한다. 그 후 L 시간이 될경우
             * 에 그동안 탐색한 갯수를 출력한다.
             *******************************/
            n = sc.nextInt();
            m = sc.nextInt();
            int r = sc.nextInt();
            int c = sc.nextInt();
            l = sc.nextInt();
            map = new int[n][m];
            visited = new boolean[n][m];
            dist = new int[n][m];
            count = 1; // 시작 맨홀 포함
            dirlist = new ArrayList[8];// 갈수있는 방향을 담는다.
            for(int i = 0; i < 8;i++) {
                dirlist[i] = new ArrayList<>();
            }
            
            for(int i = 0 ; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            dirlist[1].add(0);dirlist[1].add(1);dirlist[1].add(2);dirlist[1].add(3);
            dirlist[2].add(0);dirlist[2].add(1);
            dirlist[3].add(2);dirlist[3].add(3);
            dirlist[4].add(0);dirlist[4].add(3);
            dirlist[5].add(1);dirlist[5].add(3);
            dirlist[6].add(1);dirlist[6].add(2);
            dirlist[7].add(0);dirlist[7].add(2);
            bfs(r, c);
            System.out.println("#"+t+" "+count);
            
        }
    }
    static int[][] dist;
    static boolean[][] visited;
    static int[][][] pass= {{},{{-1,0},{1,0},{0,-1},{0,1}}, // 상,하,좌,우
                            {{-1,0},{1,0},{0,0},{0,0}},// 상,하
                            {{0,0},{0,0},{0,-1},{0,1}},// 좌,우
                            {{-1,0},{0,0},{0,0},{0,1}},// 상,우
                            {{0,0},{1,0},{0,0},{0,1}}, // 하,우
                            {{0,0},{1,0},{0,-1},{0,0}},// 하,좌 
                            {{-1,0},{0,0},{0,-1},{0,0}}};// 상,좌
    
    static int[] dir = {1,0,3,2}; // 갈수있는 방향
    static int count;
    public static void bfs(int x, int y) {
        Queue<Passage> queue= new LinkedList<>();
        
        queue.add(new Passage(x, y));
        visited[x][y] = true;
        dist[x][y] = 1;
        
        while(!queue.isEmpty()) {
            Passage p = queue.remove();
            int pnum = map[p.x][p.y];
            if(dist[p.x][p.y] == l) break;
            for(int i = 0; i < pass[pnum].length;i++) { 
                int nx = p.x+pass[pnum][i][0];
                int ny = p.y+pass[pnum][i][1];
                
                if(pass[pnum][i][0] == 0 && pass[pnum][i][1] == 0 ) continue;
                
                if(isBoundary(nx, ny) && !visited[nx][ny] && dirlist[map[nx][ny]].contains(dir[i])){
                    count++;
                    visited[nx][ny] = true;
                    dist[nx][ny] = dist[p.x][p.y] + 1;
                    queue.add(new Passage(nx, ny));
                }
            }
        }
    }
    public static boolean isBoundary(int nx,int ny) {
        if(nx >= 0 && ny >= 0 && nx < n && ny < m) 
            return true;
        return false;
    }
    static class Passage{
        int x,y;
        public Passage(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
 

 

얻은 것

• 문제를 꼼꼼히 읽자

참고 & 출처