항해 99 25일차 TIL( 게임 맵 최단거리 / 프로그래머스)

문제         

프로그래머스

1 번째 시도   

• DFS 문제
• DFS를 통해 동,서,남,북 위치 중 갈 수 있는 곳을 다 탐색한다. 
• 이때 depth로 길이를 알 수 있다.
• 계속 최소 depth를 업데이트 한다.

import java.util.*;

class Solution {
    
    int[] x  = new int[]{1,0,0,-1};
    int[] y = new int[]{0,1,-1,0};
    boolean[][] visited;
    int answer = Integer.MAX_VALUE;
    
    public int solution(int[][] maps) {
        int n = maps.length - 1;
        int m = maps[0].length - 1;
        visited = new boolean[n+1][m+1];
            
        int i =0;        
        for(int[] map: maps) {
            int j = 0;
            for(int k : map) {
                if(k == 0) visited[i][j] = true;
                j++;
            }
            i++;
        }
        
        dfs(maps,1, n, m, 0, 0);
        return (answer == Integer.MAX_VALUE) ? -1 : answer;
    }
    
    public void dfs(int[][] maps, int depth, int n, int m, int px, int py) {
        visited[py][px] = true;
        if(px == m && py == n) {
            answer = Math.min(depth, answer);
        } 
        for(int i =0; i < 4; i++) {
            if(px+x[i] >=0 && px+x[i] <= m && py+y[i] >=0 && py+y[i] <= n) {
                if(!visited[py+y[i]][px+x[i]]){
                    int nextX = px+x[i];
                    int nextY = py+y[i];
                   dfs(maps, depth+1, n, m, nextX, nextY);
                }
            }
        }
    }
}

 

2 번째 시도   

• dfs 함수를 재귀호출하고 visted[] = false 부분을 빠트린 부분 수정
  • visited[py][px] = false; 문은 노드에서 가능한 모든 방향을 탐색한 후 추가되었으며, 이는 다른 경로가 이 노드를 다시 고려할 수 있도록 하는 데 중요하다.
• (if (깊이 >= 응답) return;)은 현재 경로 깊이가 지금까지 발견된 최소 경로를 이미 초과한 경우 DFS가 추가 탐색을 중지한다. 이렇게 하면 불필요한 재귀가 줄어들고 성능 관리에 도움된다.

import java.util.*;

class Solution {
    
    int[] x  = new int[]{1,0,0,-1};
    int[] y = new int[]{0,1,-1,0};
    boolean[][] visited;
    int answer = Integer.MAX_VALUE;
    
    public int solution(int[][] maps) {
        int n = maps.length - 1;
        int m = maps[0].length - 1;
        visited = new boolean[n+1][m+1];
            
        int i =0;        
        for(int[] map: maps) {
            int j = 0;
            for(int k : map) {
                if(k == 0) visited[i][j] = true;
                j++;
            }
            i++;
        }
        
        dfs(maps,1, n, m, 0, 0);
        return (answer == Integer.MAX_VALUE) ? -1 : answer;
    }
    
    public void dfs(int[][] maps, int depth, int n, int m, int px, int py) {
        if (depth >= answer) {
            return;
        }

        visited[py][px] = true;

        if (px == m && py == n) {
            answer = Math.min(depth, answer);
            visited[py][px] = false;  
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextX = px + x[i];
            int nextY = py + y[i];

            if (nextX >= 0 && nextX <= m && nextY >= 0 && nextY <= n && maps[nextY][nextX] == 1 && !visited[nextY][nextX]) {
                dfs(maps, depth + 1, n, m, nextX, nextY);
            }
        }

        visited[py][px] = false;
    
    }
}

 

정확성은 다 통과했지만 효율성에서 다 시간 초과가 떴다.

 

3 번째 시도   

• 최단 경로 찾기는 BFS
  • DFS는 역추적 전에 가지를 따라 최대한 멀리 탐색합니다. 이는 가능한 모든 근처 옵션을 먼저 탐색하려는 최단 경로 문제에는 적합하지 않습니다. 이로 인해 특히 대규모 그리드에서 최적이 아닌 경로를 불필요하게 탐색하게 될 수 있습니다.
• 두 갈림길 상황에서
  
  • DFS는 한쪽을 끝까지 갔다고 돌아와서 다른 갈림길을 탐색
  • BFS는 두 갈림길을 번갈아가며 한 칸씩 전진하며 탐색

import java.util.*;

class Solution {

    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        boolean[][] visited = new boolean[n][m];
        int[] dx = {1, 0, 0, -1};
        int[] dy = {0, 1, -1, 0};

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 1});  
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int depth = current[2];

            if (x == m - 1 && y == n - 1) {
                return depth;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && maps[ny][nx] == 1 && !visited[ny][nx]) {
                    visited[ny][nx] = true;
                    queue.add(new int[]{nx, ny, depth + 1});
                }
            }
        }
        
        return -1;  
    }
}