[소프티어] 나무 섭지 자바 풀이 bfs (시간초과, 런타임에러, 히든테케 해결 완료)

https://softeer.ai/practice/7726

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

 

 

 

핵심 설명

1. bfs를 사용해서 (사람 혹은 유령) 과 (출구) 의 최단거리를 구해서 비교하면 된다.

2. 사람이 먼저 도착하면 Yes 출력 아니면 No 출력

 

 

이슈 4가지

1. 유령은 벽을 통과할 수 있게 분기처리 해주자. (기본조건)

이걸 안해주니 2번째 테케가 아마 틀렸었던거같습니다

4 6
...#.D
...#..
.GN#..
G.....

                if(map[nx][ny] == '#' && !ghostFlag){ // 사람은 벽 이동불가, 유령은 통과가능 (이슈1)
                    continue;
                }

 

그래도 다음과 같이 시간초과가 발생했습니다.

 

2. bfs로 완탐하기전에 목적지 위치와의 최단거리를 찾자마자 while문을 종료 시켜주자. (시간초과 미세하게 해결)

시간초과를 해결하고자 추가했던 내용인데 속시원하게 해결되진 않았습니다.

                if(dis[dest.x][dest.y] != 0){   // 목적지 발견시 바로 종료 (이슈2)
                    return dis[dest.x][dest.y];
                }

 

 

3. 유령은 출구에서 가장 가까운 한명만 찾아주자. (피타고라스의 정리 a2 + b2 = c2  이용) (시간초과 완전 해결)

2번만으로는 시간초과가 줄지 않아서, 원인을 찾다가 3번을 적용하니 런타임에러 제외하고 전부 테케 통과했습니다.

        int selectGhost = 0;
        int disGhostAndExit = Integer.MAX_VALUE;
        for(int i=0; i<ghost.size(); i++){
            int a = Math.abs(dest.x-ghost.get(i).x);
            int b = Math.abs(dest.y-ghost.get(i).y);
            if( disGhostAndExit > (a*a)+(b*b) ){
                disGhostAndExit = (a*a)+(b*b);
                selectGhost = i;
            }
        }

 

4. 유령이 없는 경우를 예외처리 해주자. (소프티어 '연습문제 톡' 에 누가 이의제기 글 올려서 테케가 추가된것같네요) (히든 테케)

런타임에러 발생시 실행결과 상세보기 버튼 클릭해서 보면

마지막 5개의 테스트케이스가 런타임에러일테고

아마 본 이슈처럼 유령이 없는 경우의 케이스일거라고 보여지네요

 

        // 이슈4 유령 없을때 예외처리 추가
        if(!ghost.isEmpty())
            ghostCnt = bfs(map, ghost.get(selectGhost), dest, true);
        else
            ghostCnt = Integer.MAX_VALUE;

 

 

 

 

핵심 코드

"이슈" 로 검색해보시면 쉽게 찾으실 수 있습니다.

 

 

 

 

 

전체 코드

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

public class Main {

    public static int dx[] = {-1, 0, 1, 0};
    public static int dy[] = {0, 1, 0, -1};

    public static class Point{
        int x;
        int y;

        public Point() {

        }

        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int dap = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        char map[][] = new char[n][m];
        Point nam = new Point();
        Point dest = new Point();
        ArrayList<Point> ghost = new ArrayList<>();

        for(int i=0; i<n; i++){
            String line = br.readLine();
            for(int j=0; j<m; j++){
                char c = line.charAt(j);
                // System.out.print(c);
                map[i][j] = c;

                if(c == 'N'){
                    nam.x = i; nam.y = j;
                }
                if(c == 'D'){
                    dest.x = i; dest.y = j;
                }
                if(c == 'G'){
                    ghost.add(new Point(i, j));
                }
            }
            // System.out.println();
        }

        int namCnt = bfs(map, nam, dest, false);
        // System.out.println("namCnt : " + namCnt);



        int ghostCnt = Integer.MAX_VALUE;
        // 유령 전체 다 bfs 돌리니 시간초과 발생 (이슈3)
//        for(int i=0; i<ghost.size(); i++){
//            int calCnt = bfs(map, ghost.get(i), dest, true);
//            // System.out.println("calCnt[" + i + "] : " + calCnt);
//            ghostCnt = Math.min(ghostCnt, calCnt);
//        }
        // x,y 좌표 계산해서 출구랑 가장 가까운 거리의 유령을 찾고 그녀석만 비교해주자
        int selectGhost = 0;
        int disGhostAndExit = Integer.MAX_VALUE;
        for(int i=0; i<ghost.size(); i++){
            int a = Math.abs(dest.x-ghost.get(i).x);
            int b = Math.abs(dest.y-ghost.get(i).y);
            if( disGhostAndExit > (a*a)+(b*b) ){
                disGhostAndExit = (a*a)+(b*b);
                selectGhost = i;
            }
        }
        // 이슈4 유령 없을때 예외처리 추가
        if(!ghost.isEmpty())
            ghostCnt = bfs(map, ghost.get(selectGhost), dest, true);
        else
            ghostCnt = Integer.MAX_VALUE;
        // System.out.println("ghostCnt[" + selectGhost + "] : " + ghostCnt);



        // 출력
        if(namCnt < ghostCnt && namCnt != 0){
            bw.write("Yes");
        }else{
            bw.write("No");
        }

        bw.flush();
        bw.close();
    }

    public static int bfs(char map[][], Point mop, Point dest, boolean ghostFlag){

        boolean v[][] = new boolean[map.length][map[0].length];
        int dis[][] = new int[map.length][map[0].length];
        for(int i=0; i<map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                v[i][j] = false;
                dis[i][j] = 0;
            }
        }

        // 시작위치 방문표시하고 큐에 추가
        v[mop.x][mop.y] = true;
        Queue<Point> q = new LinkedList<>();
        q.add(mop);

        // 큐에서 하나씩 꺼내면서 너비탐색 시작
        while(!q.isEmpty()){
            Point cur = q.poll();

//            System.out.println();
//            for(int i=0; i<map.length; i++){
//                for(int j=0; j<map[0].length; j++){
//                    System.out.print(dis[i][j] + " ");
//                }
//                System.out.println();
//            }

            // 상하좌우로 이동해볼건데
            for(int i=0; i<4; i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length){  // 맵에서 벗어나지 않고
                    continue;
                }
                // System.out.println("(" + nx + ", " + ny + ")" + " : " + dis[nx][ny]);
                if(v[nx][ny] == true){ // 기방문은 이동불가
                    continue;
                }
                if(map[nx][ny] == '#' && !ghostFlag){ // 사람은 벽 이동불가, 유령은 통과가능 (이슈1)
                    continue;
                }

                v[nx][ny] = true;
                dis[nx][ny] = dis[cur.x][cur.y]+1;
                if(dis[dest.x][dest.y] != 0){   // 목적지 발견시 바로 종료 (이슈2)
                    return dis[dest.x][dest.y];
                }
                q.add(new Point(nx, ny));
            }
        }
        return dis[dest.x][dest.y];
    }
}