[소프티어] 나무 섭지 풀이에 관하여.java

https://softeer.ai/practice/7726

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

✍문제 해결 핵심 전략탈출 여부의 요인 정확히 분석하기

1. 남우가 탈출하기 위해서는 유령에게 잡히지 않고 탈출구를 찾아가야 합니다.
2. 남우와 유령 사이의 관계 명확히 파악하기 (벽 넘기의 유무)

 

 

 

🔍'유령에게 잡히지 않는다'

 

▶ 유령보다 탈출구에 더 빨리 도착해야한다.

 

🔍'탈출구를 찾아간다.'

 

▶ 탐색을 통해 탈출구에 도달할 수 있는가?.

 

🔍'벽을 넘을 수 있다.'를 위의 내용과 연관시키면

 

▶ 벽의 유무를 고려한 뒤 남우가 최단거리로 출구에 가야 한다.

 

 

 

 

한 줄 요약

 

유령과 탈출구 사이 거리, 남우와 탈출구 사이 거리 (남우는 벽을 고려)

비교를 통해 탈출의 유무를 확인할 수 있다.

 

 

 

 

 

👨‍💻Code 구현

import java.util.*;

public class Softeer_나무섭지 {
    static int Dr, Dc, Nr, Nc, Wr, Wc, ghost_num, n, m, Min_distanceDoortoGhost,Min_distanceDoortoNam, distanceDoortoNam;
    static int[] dr = {0, -1, 0, 1};
    static int[] dc = {-1, 0, 1, 0};

    static int[][] visited ;
    static char[][] maze;
    static List<int[]> ghostPos = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt(); //행
        m = sc.nextInt(); //열

        maze = new char[n][m];
        visited = new int[n][m];
        ghost_num = 0;
        Dr = 0;Dc = 0;
        Nr = 0;Nc = 0;
        Wr = 0;Wc = 0;
        Min_distanceDoortoGhost = Integer.MAX_VALUE;
        Min_distanceDoortoNam = Integer.MAX_VALUE ;
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            for (int j = 0; j < m; j++) {
                maze[i][j] = str.charAt(j);
                if (maze[i][j] == 'G') {
                    int[] arr = new int[2];
                    arr[0] = i;
                    arr[1] = j;
                    ghostPos.add(arr);
                    ghost_num++;
                } else if (maze[i][j] == 'D') {
                    Dr = i;
                    Dc = j;
                } else if (maze[i][j] == 'N') {
                    Nr = i;
                    Nc = j;
                } else if (maze[i][j] == '#') {
                    Wr = i;
                    Wc = j;
                }
            }
        }// idx 미리 찾기

        //유령과 문사이 최소거리 구하기
        for (int ghost = 0; ghost < ghost_num; ghost++) {
            int[] arr = ghostPos.get(ghost);
            int sum = Math.abs(Dr - arr[0]) + Math.abs(Dc - arr[1]);

            if (sum < Min_distanceDoortoGhost)
                Min_distanceDoortoGhost = sum;
        }

        if (cal_distanceDoortoNam(Nr, Nc) > 0 && cal_distanceDoortoNam(Nr, Nc) < Min_distanceDoortoGhost)
            System.out.println("Yes");
        else System.out.println("No");
    }
    public static int cal_distanceDoortoNam( int Nr, int Nc) { //BFS로 칸마다 걸리는 이동 거리 확인하기

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{Nr,Nc});
        visited[Nr][Nc] = 0;

        while (!q.isEmpty()){
            int[] currentNam = q.poll();
            int curR = currentNam[0];
            int curC = currentNam[1];
            for(int i =0; i<4 ; i++){
                int nR = curR + dr[i];
                int nC = curC + dc[i];

                if(nR >= n || nR < 0 || nC >= m || nC < 0 || maze[nR][nC] == '#') continue; //경계조건 or 벽 발견

                if(visited[nR][nC] == 0 ){
                    visited[nR][nC] = visited[curR][curC] + 1 ; //이동한 거리를 칸마다 갱신한다.
                    q.add(new int[]{nR,nC}); 
                }
            }
        }
        return visited[Dr][Dc];
    }
}