[프로그래머스 | Java Lv.2] 게임 맵 최단거리 (DFS/BFS)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

---

접근

일반적인 dfs/bfs 문제였다. dfs로 구현을 했었지만 까먹었던 부분이 최단 경로를 찾는 문제에서는 bfs가 더 적합하다는 것이었다. dfs는 모든 경로를 탐색하는 알고리즘이기 때문에 도착점에 도달하는 순간 종료되는 bfs를 이용하는 게 좋다. 

이 문제는 dfs로 풀 경우 테스트 케이스는 모두 통과하지만 효율성 테스트에서 모두 실패가 뜬다. 

 

첫번째 제출 -  DFS 이용, 시간 초과

package week4.baek.dfsbfs;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;

public class GameMap {
    static int n;
    static int m;
    static ArrayList<Integer> result;
    static boolean[][] visited;

    public static void dfs(int x, int y, int count, int[][] maps){
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        //방문 처리
        visited[y][x] = true;

        //도착지에 도달했다면
        if(x == n-1 && y == m-1)  {
            result.add(count);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= 0 && nx < n && ny >= 0 && ny < m){
                if(!visited[ny][nx] && maps[ny][nx] == 1) {
                    visited[ny][nx] = true;
                    dfs(nx, ny, count + 1, maps);
                    visited[ny][nx] = false;
                }
            }
        }
    }

    public static int solution(int[][] maps) {
        result = new ArrayList<>();

        //세로 길이
        m = maps.length;
        //가로 길이
        n = maps[0].length;

        visited = new boolean[m][n];

        dfs(0, 0, 1, maps);

        Collections.sort(result);

        if(result.size() == 0)  return -1;

        return result.get(0);
    }

    public static void main(String[] args) {
        int[][] maps = {{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,1},{0,0,0,0,1}};
        System.out.println(solution(maps));
    }
}

---

최종 코드 - bfs 사용

package week4.baek.dfsbfs;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class GameMap {
    static int n;
    static int m;
    static ArrayList<Integer> result;
    static boolean[][] visited;
    static int answer = -1;

    public static void bfs(int x, int y, int[][] maps){
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        visited[y][x] = true;

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

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

            if(x == n-1 && y == m-1) {
                answer = count;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(maps[ny][nx] == 0) continue;
                if(!visited[ny][nx] && maps[ny][nx] == 1) {
                    visited[ny][nx] = true;
                    queue.add(new int[]{nx, ny, count+1});
                }
            }
        }



    }

    public static int solution(int[][] maps) {
        //세로 길이
        m = maps.length;
        //가로 길이
        n = maps[0].length;

        visited = new boolean[m][n];

         bfs(0, 0,  maps);

        return answer;


    }

    public static void main(String[] args) {
        int[][] maps = {{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,1},{0,0,0,0,1}};
        System.out.println(solution(maps));
    }
}

---

참고

https://141227.tistory.com/301

[DFS/BFS] 프로그래머스 1844번 게임 맵 최단거리(Java)