[2주차] 게임 맵 최단거리

https://programmers.co.kr/learn/courses/30/lessons/1844?language=java 

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

---

이런 길찾기 문제는 BFS와 DFS로 해결이 가능하다

 

DFS(Depth First Search, 깊이 우선 탐색)을 통해 경로를 찾는 경우 BFS(Breath Frist Search, 넓이 우선 탐색)에 비해 평균적으로 경로 탐색 시간이 더 걸린다.

DFS의 경우 가능한 모든 경로를 간 후 가장 최단거리를 구하는 반면 BFS는 맨처음 도착한 경로가 가장 최단거리가 되기 떄문이다!

 

그래서 나도 BFS를 사용하여 문제를 풀었고, 최단 거리가 얼마인지는 배열의 원소를 이전에 지나온 원소 + 1을 해서 바꿔주는 식으로 구현하였다

 

그리고 이렇게 상하좌우로 움직이는 경우에는 dx와 dy를 지정해서 이동하는게 편하다고 해서 이전에 풀었던 풀이를 참고해서 풀었다

그래도 아직 이전 풀이를 안보면 완벽하게 혼자서는 못풀겠다ㅠ

다시 풀어봐야지!!

 

 

자바 코드)

import java.util.*;
public class comu2_2 {
    static int n;
    static int m;
    static 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}};
    static boolean[][] visited;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static public int solution(int[][] maps) {
        int answer = 0;
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];


        visited[0][0] = true;
        bfs(0, 0);
        System.out.println(maps[n-1][m-1]);
        return answer;
    }

    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        boolean end = false;

        while(!q.isEmpty()) {
            int now[] = q.poll();
            int nx = now[0];
            int ny = now[1];

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

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


    public static void main(String[] args) {
        solution(maps);
    }

}