[프로그래머스] lv2. 게임 맵 최단 거리 [#DFS #BFS]

 

 

 

---

1. 문제 출처

---

 

프로그래머스

 

 

 

 

---

2. 설계

---

 

- 첫번째 방법처럼 동서남북으로 이동해  최대한 빠르게 상대방 진영(5,5)까지 진출하는 것이다.

 

 

 

- 이렇게 상대방 진영에 진입하지 못할 수도 있다.

 

 

- BFS를 사용해 가장 빠른 DEPTH로 도착하는 정답을 구하자 (아래와 같다)

- 단 갔던 길은 다시 못가게 visited 배열을 관리할 필요가 있다.

 

 

---

3. 전체 코드

---

import java.util.*;

class Solution {
    
    //상하좌우
    static int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};
    static int rowLength;
    static int colLength;
    
    static int answer = 987654321;
    public static class location{
        int x;
        int y;
        int depth;
        public location(int x, int y, int depth){
            this.x=x;
            this.y=y;
            this.depth=depth;
            
        }
    }
    public int solution(int[][] maps) {
        rowLength = maps.length;
        colLength = maps[0].length;
        boolean[][] visited = new boolean[rowLength][colLength];
        bfs(maps,visited);
        
        if(answer==987654321) answer=-1;
        return answer;
    }
    
    public static void bfs(int[][] maps, boolean[][] visited){
        
        Queue<location> q = new LinkedList<>();
        q.offer(new location(0,0,1));
        visited[0][0]=true;
        
        while(!q.isEmpty()){
            location cur = q.poll();
            
            if(cur.x==rowLength-1 && cur.y==colLength-1){
                answer = Math.min(answer, cur.depth);
            }
            
            for(int d=0;d<4;d++){
                int nextX = cur.x+direction[d][0];
                int nextY = cur.y+direction[d][1];
                if(nextX<0 || nextX>=rowLength || nextY<0 || nextY>=colLength) continue;
                if(maps[nextX][nextY]==0 || visited[nextX][nextY]) continue;
                
                q.offer(new location(nextX, nextY, cur.depth+1));
                visited[nextX][nextY]=true;
            }
        }
        
    }
    
}

 

주의점은 maps의 크기가 5x5로 고정이 아니라는 것이다.

 

 

 

 

---

4. DFS로 안되는 이유

---

DFS는 시스템 스택을 이용하기 때문에 BFS보다 시간이 더 걸리는데, 정답은 다 맞아도 효율성에서 시간 초과가 난다.

import java.util.*;

class Solution {
    
    //상하좌우
    static int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};
    // static boolean[][] visited = new boolean[5][5];
    static int rowLength;
    static int colLength;
    
    static int answer = 987654321;
    public static class location{
        int x;
        int y;
        int depth;
        public location(int x, int y, int depth){
            this.x=x;
            this.y=y;
            this.depth=depth;
            
        }
    }
    public int solution(int[][] maps) {
        rowLength = maps.length;
        colLength = maps[0].length;
        boolean[][] visited = new boolean[rowLength][colLength];
        // visited[0][0]=true;
        bfs(maps,visited);
        // dfs(maps,visited, 0, 0, 1);
        
        if(answer==987654321) answer=-1;
        return answer;
    }
    
    public static void bfs(int[][] maps, boolean[][] visited){
        
        Queue<location> q = new LinkedList<>();
        q.offer(new location(0,0,1));
        visited[0][0]=true;
        
        while(!q.isEmpty()){
            location cur = q.poll();
            
            if(cur.x==rowLength-1 && cur.y==colLength-1){
                answer = Math.min(answer, cur.depth);
            }
            
            for(int d=0;d<4;d++){
                int nextX = cur.x+direction[d][0];
                int nextY = cur.y+direction[d][1];
                if(nextX<0 || nextX>=rowLength || nextY<0 || nextY>=colLength) continue;
                if(maps[nextX][nextY]==0 || visited[nextX][nextY]) continue;
                
                q.offer(new location(nextX, nextY, cur.depth+1));
                visited[nextX][nextY]=true;
            }
        }
        
    }
    
//     public static void dfs(int[][] maps, boolean[][] visited, int x, int y, int count){
        
//         if(x==rowLength-1 && y==colLength-1){
//             answer = Math.min(answer, count);
//             return;
//         }
        
//         for(int d=0;d<4;d++){
//             int nextX = x+direction[d][0];
//             int nextY = y+direction[d][1];
            
            
//             if(nextX<0 || nextX>=rowLength || nextY<0 || nextY>=colLength) continue;
//             if(maps[nextX][nextY]==0 || visited[nextX][nextY]) continue;
            
            
            
//             visited[nextX][nextY]=true;
//             dfs(maps, visited, nextX, nextY, count+1);
//             visited[nextX][nextY]=false;
//         }
        
//     }
}

 

DFS로도 풀었지만, 효율성에서 모두 시간초과가 나서 주석처리한 모습 :)