프로그래머스 - 게임 맵 최단거리

dfs로 풀어보기

처음에는 dfs로 풀어보았다. 일반적으로는 dfs보다는 bfs가 더 빠르니 이런 문제가 나오면 bfs로 풀어보도록 하자

import java.util.*;

class Solution {
    int n;
    int m;
    int ans=Integer.MAX_VALUE;
    int[] fx = new int[] {0,0,1,-1};
    int[] fy = new int[] {1,-1,0,0};
    public int solution(int[][] maps) {
        
        n=maps.length;
        m=maps[0].length;
        
        boolean[][] check = new boolean[n][m];
        check[0][0]=true;
        
        dfs(0,0,maps,check,1);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    
    public void dfs(int x, int y,int[][] maps,boolean[][] check,int answer) {
    
        if (x == m-1 && y == n-1) {
            ans = Math.min(ans,answer);
            return;
        };
        
        for (int i=0;i<4;i++) {
            int nx = fx[i] + x;
            int ny = fy[i] + y;
            if (nx >=0 && nx<m && ny>=0 && ny<n && !check[ny][nx] && maps[ny][nx]==1) {
                check[ny][nx] = true;
                dfs(nx,ny,maps,check,answer+1);
                check[ny][nx] = false;
            }
        };
        
        
    }
}

bfs로 풀어보기

import java.util.*;

class Solution {
    int n;
    int m;
    int ans=Integer.MAX_VALUE;
    int[] fx = new int[] {0,0,1,-1};
    int[] fy = new int[] {1,-1,0,0};
    public int solution(int[][] maps) {

        n=maps.length;
        m=maps[0].length;

        int[][] visited = new int[n][m];

        bfs(maps,visited);
        return visited[n-1][m-1] == 0 ? -1 :visited[n-1][m-1];
    }

        void bfs(int[][] maps, int[][] visited) {
            int x = 0;
            int y = 0;
            visited[x][y] = 1;
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{x, y});

            while (!queue.isEmpty()) {
                int[] cur = queue.poll();

                for (int i=0;i<4;i++) {
                    int nx = cur[0] + fx[i];
                    int ny = cur[1] + fy[i];
                    if (nx >=0 && nx< m && ny>=0 && ny <n && maps[ny][nx]==1 && visited[ny][nx]==0) {
                        visited[ny][nx] = visited[cur[1]][cur[0]] +1;
                        queue.offer(new int[]{nx,ny});
                    }
                }
            }

        }


    }

출처 : 프로그래머스 알고리즘
참고 블로그 : tistory - G-GI