[Softeer] 나무 섭지

문제

링크 : https://softeer.ai/practice/7726

사용 언어 : JAVA

---

아무튼 유령에게 잡히지 않고 남우가 탈출할 수 있다면 Yes, 못한다면 No를 출력

---

내 생각

초기 생각

유령은 필요에 따라 이동하지 않아도 되므로, 그냥 남우는 냅두고 최대한 빨리 탈출구로 가서 버티면 된다고 생각했다. 그래서 남우가_탈출구에_도착하는_시간(bfs) >= 유령이_탈출구에_도착하는_시간이라면 남우는 반드시 탈출 할 수 없을 것이라고 생각했다.

MIN = 남우~출구까지의 최단 거리

for 유령: 유령들
	min = Math.abs(유령.x - 출구.x) + Math.abs(유령.y - 출구.y)
    min <= MIN 이면 No 출력
    
아니면 Yes 출력

하지만 코드를 제출하니 계속 틀렸다고 떴고.. 내 생각에 문제가 있음을 깨달았다.

 

개선

요점은 "남우가_탈출구에_도착하는_시간(bfs) >= 유령이_탈출구에_도착하는_시간이라면 남우는 반드시 탈출 할 수 없다"는 맞지만 "남우가_탈출구에_도착하는_시간(bfs)< 유령이_탈출구에_도착하는_시간이어도 남우는 탈출 못할 수도 있다"는 것이다.

왜냐.. 내가 처음에 생각한 방식은 남우가 움직이는 동안 유령들은 암것도 안하고 우두커니 지켜보고 있어야 성립하기 때문이다...ㅋㅋㅋㅋ 남우가 bfs로 열심히 탈출구를 찾아도 유령도 함께 움직이기 때문에 가야할 곳을 못가는 경우가 생긴다!!!!!

여튼 그래서 코드를 다시 짰다ㅠㅠ 이번에는 유령을 먼저 움직여서 구역당 걸리는 시간을 체크하고, 여러 구역 중 남우가 유령보다 빨리 도착할 수 있는 구역만을 사용하여 탈출 루트를 만들었다.

 

최종 코드

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

public class Main {
    public static int N, M;
    public static char[][] map;
    public static int[] nam, exit;
    public static int[][] nVst, gVst;	// 구역까지 가는데 걸리는 시간
    public static ArrayList<int[]> ghosts = new ArrayList<>();

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        map = new char[N][M];
        nVst = new int[N][M];
        gVst = new int[N][M];

        // 맵 정보 받아옴
        for(int i=0; i<N; i++) {
            String line = br.readLine();
            map[i] = line.toCharArray();

            if(line.contains("D"))
                exit = new int[]{i, line.indexOf('D')};
            if(line.contains("N")) {
                nam = new int[]{i, line.indexOf('N')};
                nVst[nam[0]][nam[1]] = 1;
            }
            if(line.contains("G")) {
                ghosts.add(new int[]{i, line.indexOf('G')});
                gVst[i][line.indexOf('G')] = 1;
            }
        }

        // 먼저 유령이 맵을 이동하는데 걸리는 시간을 계산
        ghostMove();

        // bfs로 남우 탈출경로 찾기
        // 이동 가능 경우
        // -> 경계 내부, 벽이 아닌 비어 있는 공간
        // -> **유령보다 먼저 도달할 수 있는 곳**
        // 만약 중간에 이동할 수 있는 곳이 없다면 탈출 실패
        if(!namMove()){
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }

    private static void ghostMove() {
        Queue<int[]> queue = new LinkedList<>();
        for(int[] ghost: ghosts) {
            queue.add(ghost);
        }
        bfs(queue, true, gVst);
    }

    private static boolean namMove() {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(nam);
        int ret = bfs(queue, false, nVst);
        if(ret == Integer.MAX_VALUE) return false;
        return true;
    }

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

    private static int bfs(Queue<int[]> queue, boolean isGhost, int[][] visited) {
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                
                // 갈 수 있는지
                if(!canMove(nr, nc, isGhost, visited[r][c], visited)) continue;
                
                // 지금보다 1초 더 걸림
                visited[nr][nc] = visited[r][c] + 1;
                queue.add(new int[]{nr, nc});
                
                // 남우) 이동할 곳이 출구라면 바로 종료. 걸린 시간 반환
                if(!isGhost && nr==exit[0] && nc==exit[1]) return visited[nr][nc];
            }
        }

	// 남우) 이동할 수 없게 되면 INF 반환
        return Integer.MAX_VALUE;
    }

    private static boolean canMove(int nr, int nc, boolean isGhost, int prev, int[][] visited) {
    	// 경계 내부인가? 이전에 방문한 적이 없는가?
        if(nr<0 || nr>=N || nc<0 || nc>=M) return false;
        if(visited[nr][nc] != 0) return false;
        // 유령이면 OK
        if(isGhost) return true;
        
        // 남우만 해당. 벽인가? 유령보다 빨리 도달할 수 없는 곳인가?
        if(map[nr][nc] == '#') return false;
        if(gVst[nr][nc] <= prev + 1) return false;
        return true;
    }
}

---

느낀점

• ...