[Java] 프로그래머스 - 게임 맵 최단거리 (2단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

코딩테스트 연습 - 게임 맵 최단거리

 

 

 

 

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int row = maps.length;
        int col = maps[0].length;
        boolean[][] check = new boolean[row][col]; //다녀왔는지 체크용
        
        //BFS를 구현하기 위한 큐
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0, 1));
        
        //상하좌우 움직일 배열
        int[] xMove = {1, -1, 0, 0};
        int[] yMove = {0, 0, -1, 1};
        
        while (!q.isEmpty()) {
            Point p = q.poll();
            int x = p.x;
            int y = p.y;
            int num = p.num;
            
            //만약 x, y가 상대팀 진영이라면 num 리턴하기
            if (x == row - 1 && y == col - 1) return num;
            
            for (int i = 0; i < 4; i++) {
                int xm = x + xMove[i];
                int ym = y + yMove[i];
                
                //움직일 좌표가 범위를 넘진 않았는지, 이미 방문한 좌표인지, 해당 좌표가 벽인지 파악
                if (xm < 0 || ym < 0 || xm >= row || ym >= col) continue;
                if (check[xm][ym] || maps[xm][ym] == 0) continue;
                
                //방문 체크하고 q에 추가하기
                check[xm][ym] = true;
                q.add(new Point(xm, ym, num+1));
            }
        }
        
        //while문을 통과했는데도 리턴되지 않았다면 그냥 -1 리턴
        return -1;
    }
}

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

 

정확성 테스트

테스트 1 〉	통과 (0.31ms, 78.5MB)
테스트 2 〉	통과 (0.26ms, 77.7MB)
테스트 3 〉	통과 (0.32ms, 78.9MB)
테스트 4 〉	통과 (0.29ms, 73.9MB)
테스트 5 〉	통과 (0.30ms, 67.5MB)
테스트 6 〉	통과 (0.29ms, 76.5MB)
테스트 7 〉	통과 (0.37ms, 79.4MB)
테스트 8 〉	통과 (0.29ms, 71.7MB)
테스트 9 〉	통과 (0.38ms, 86.7MB)
테스트 10 〉	통과 (0.44ms, 67.1MB)
테스트 11 〉	통과 (0.30ms, 77.6MB)
테스트 12 〉	통과 (0.31ms, 73.1MB)
테스트 13 〉	통과 (0.44ms, 75.5MB)
테스트 14 〉	통과 (0.40ms, 77.4MB)
테스트 15 〉	통과 (0.28ms, 71.2MB)
테스트 16 〉	통과 (0.39ms, 76.8MB)
테스트 17 〉	통과 (0.41ms, 78.7MB)
테스트 18 〉	통과 (0.26ms, 71.7MB)
테스트 19 〉	통과 (0.36ms, 73.6MB)
테스트 20 〉	통과 (0.32ms, 68.5MB)
테스트 21 〉	통과 (0.26ms, 75.3MB)

효율성 테스트

테스트 1 〉	통과 (10.62ms, 52.9MB)
테스트 2 〉	통과 (3.84ms, 54.3MB)
테스트 3 〉	통과 (9.10ms, 56MB)
테스트 4 〉	통과 (4.86ms, 56.2MB)

 

 

 

 

 

DFS로 풀면 효율성 테스트에서 시간초과가 나오고, BFS로 풀어야 통과함