1953번 - 탈주범 검거

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

전형적인 BFS 문제이다.

기준점으로부터 1씩 이동하면서 방문했던 곳을 체크하며 카운트를 하면 된다.

근데 나는... 아직도 BFS보단 DFS가 편해서 DFS로 풀었다.

DFS로 풀려면 방문했던 곳을 체크하는 거로 문제를 풀 수 없다.

한 번 방문했던 곳보다 더 빠른 루트가 있을 수 있기 때문이다.

 

 

DFS로 풀 때 신경써줘야 하는 예시

 

예를 들어 DFS로 파란색 루트를 먼저 탐색했다고 치자.

 

 

이미 방문처리가 되어 주황색 루트로 탐색이 불가능하다

 

주황색 루트로 탐색하면 더 빠르게 도착하고, 주어진 시간 내에 더 먼 거리까지 도달할 수 있을 텐데

이미 방문처리가 되어 탐색이 막히는 모습이다.

난 이 부분을 미처 생각하지 못해 삽질을 좀 했다.

 

 

처음 위치로 부터의 거리를 저장한 모습

 

그래서 나는 visited 대신 처음 위치와의 거리를 저장했다.

이렇게 하면 이전에 탐색했던 루트의 거리와 현재 탐색 중인 루트의 거리를 비교할 수 있다.

위 예시에서는 2와 6을 비교하여 주황색 루트로 탐색하는 것이 가능해진다.

필요 없어진 값 6은 2로 덮어버리면 된다.

 

        pipes[1] = new Pipe(true, true, true, true);
        pipes[2] = new Pipe(true, true, false, false);
        pipes[3] = new Pipe(false, false, true, true);
        pipes[4] = new Pipe(true, false, false, true);
        pipes[5] = new Pipe(false, true, false, true);
        pipes[6] = new Pipe(false, true, true, false);
        pipes[7] = new Pipe(true, false, true, false);

파이프 같은 경우는 난 이렇게 저장했다.

Pipe 클래스를 하나 만들고 상, 하, 좌, 우 값을 true/false로 넣었다.

위쪽이 뚫려있으면 true 막혀있으면 false 이런 식

 

public boolean isConnected(Pipe p, int direc) {
        if (direc == 0 && this.U && p.D) { // 위쪽
            return true;
        } else if (direc == 1 && this.D && p.U) { // 어래쪽
            return true;
        } else if (direc == 2 && this.L && p.R) { // 왼쪽
            return true;
        } else if (direc == 3 && this.R && p.L) { // 오른쪽
            return true;
        }
 
        return false;
    }

연결되어 있는지 여부는 방향을 이용했다.

방향(direc)에 맞는 현재 위치의 파이프와 다음 위치의 파이프가 뚫려있는지를 체크했다.

위쪽 방향으로 파이프가 연결되려면

현재 파이프의 위쪽 방향과 다음 파이프의 아래쪽 방향이 뚫려있는지 검사. 이런 식이다.

 

 

2. 코드

public class Solution {
    static int[][] map;
    static int[][] log;
    static Pipe[] pipes = new Pipe[8];
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static int N, M, L, pos;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int testCase = Integer.parseInt(br.readLine());
 
        init();
 
        for (int tc = 1; tc <= testCase; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 세로 크기
            M = Integer.parseInt(st.nextToken()); // 가로 크기
            int R = Integer.parseInt(st.nextToken()); // 맨홀 세로 위치
            int C = Integer.parseInt(st.nextToken()); // 맨홀 가로 위치
            L = Integer.parseInt(st.nextToken()); // 시간
 
            map = new int[N][M];
            log = new int[N][M];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    log[i][j] = Integer.MAX_VALUE;
                }
            }
 
            pos = 0;
            dfs(R, C, 1);
 
            sb.append("#").append(tc).append(" ").append(pos).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
 
    public static void init() {
        pipes[1] = new Pipe(true, true, true, true);
        pipes[2] = new Pipe(true, true, false, false);
        pipes[3] = new Pipe(false, false, true, true);
        pipes[4] = new Pipe(true, false, false, true);
        pipes[5] = new Pipe(false, true, false, true);
        pipes[6] = new Pipe(false, true, true, false);
        pipes[7] = new Pipe(true, false, true, false);
    }
 
    public static void dfs(int y, int x, int hour) {
        if (hour > L) return;
        if (log[y][x] == Integer.MAX_VALUE) pos++; // 초기값이 아니라면 처음 들르는 곳이니 pos++
        log[y][x] = hour;
 
        for (int i = 0; i < 4; i++) {
            int newY = y + dy[i];
            int newX = x + dx[i];
 
            if (check(y, x, newY, newX, i) && hour + 1 < log[newY][newX]) {
                dfs(newY, newX, hour + 1);
            }
        }
    }
 
    public static boolean check(int y, int x, int newY, int newX, int direc) {
        if (newY < 0 || newX < 0 || newY >= N || newX >= M) {
            return false;
        }
 
        if (map[newY][newX] == 0) {
            return false;
        }
 
        if (pipes[map[y][x]].isConnected(pipes[map[newY][newX]], direc)) {
            return true;
        }
 
        return false;
    }
}
 
class Pipe {
    boolean U;
    boolean D;
    boolean L;
    boolean R;
 
    public Pipe(boolean U, boolean D, boolean L, boolean R) {
        this.U = U;
        this.D = D;
        this.L = L;
        this.R = R;
    }
 
    public boolean isConnected(Pipe p, int direc) {
        if (direc == 0 && this.U && p.D) {
            return true;
        } else if (direc == 1 && this.D && p.U) {
            return true;
        } else if (direc == 2 && this.L && p.R) {
            return true;
        } else if (direc == 3 && this.R && p.L) {
            return true;
        }
 
        return false;
    }
}

나는 58번째 줄 때문에 많이 헤맸다.

처음 방문하는 곳만 카운트하도록 주의하자.

 

 

3. 실행시간

 

 

 

 

 

 

 

---

💡 느낀 점

• 거리가 아닌 visited를 저장해서 한참을 헤맸고, 처음 들르는 곳만 카운트해야 하는데 매번 카운트해서 또 한참 헤맸다. 웬만하면 BFS를 의도하는 문제는 BFS로 풀자...

---