데이크스트라와 bfs의 차이는?

데이크 스트라의 모습

 

비슷하면서도 쓰이는 곳이 다른 데이크스트라와 BFS(너비 우선 탐색) 

둘은 각각 어떤것이고 어떻게 쓰임을 구분해야할까?

 

• BFS(너비 우선 탐색): 시작 지점으로부터 해당 노드까지의 최소 이동 횟수를 찾는 것이다. 따라서 가중치가 없는 그래프에서 최단 경로를 찾을 때 사용된다.
• 데이크 스트라 알고리즘: 시작 노드로부터 각 노드까지의 최단 경로와 그 거리를(다른부분) 찾는 것이다. 따라서 가중치가 있는 그래프에서 최단 경로를 찾을 때 사용된다.

BFS는 최소 이동횟수를 구하는 루트를 찾는것이기에 여비가 소모된다던가 하는 가중치는 고려하지 않는다!

동일한 것으로 간주하고 큐를 사용해서 탐색하는 것이다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = 1;
        int[][] cave;//동굴 도국루피
        int[][] dist;//시작점부터 각 지점까지의 최단 거리
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int N;

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            if (N == 0) {
                break;//N이 0이면 바로종료
            }
            cave = new int[N][N];
            dist = new int[N][N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    cave[i][j] = Integer.parseInt(st.nextToken());
                    dist[i][j] = Integer.MAX_VALUE;
                    //초기 거리를 무한대로 설정(아직 최단거리를 몰라서?)
                }
            }

            PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
            //3번재 요소인 cave(잃는 루피양)에따라 정렬 그래야 최소 소모에 가까워짐
            //mz하게 람다식으로

            pq.offer(new int[]{0, 0, cave[0][0]});//시작점
            dist[0][0] = cave[0][0];

            //다익스트라 알고리즘 수행
            while (!pq.isEmpty()) {
                int[] current = pq.poll();//우선순위 큐에서 현재 위치와 비용 정보를 가져옴

                int x = current[0];
                int y = current[1];
                int cost = current[2];

                if (x == N - 1 && y == N - 1) {
                    System.out.println("Problem " + testCase + ": " + cost); // 결과 출력
                    break;
                }

                if (dist[x][y] < cost) {
                    continue;
                }

                //상하좌우 인접한 위치에 대해 최단 거리 업데이트 및 우선순위 큐에 추가
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i]; // 다음 x 좌표
                    int ny = y + dy[i]; // 다음 y 좌표

                    //다음 위치가 유효하고, 다음 위치까지의 거리가 갱신될 수 있는 경우
                    if (nx >= 0 && nx < N && ny >= 0 && ny < N
                            && dist[nx][ny] > dist[x][y] + cave[nx][ny]) {
                        dist[nx][ny] = dist[x][y] + cave[nx][ny];//최단 거리 업데이트
                        pq.offer(new int[]{nx, ny, dist[nx][ny]});//pq에 추가
                    }
                }
            }
            testCase++;
        }
        br.close();
    }

}

 

백준의 젤다 문제같은경우도 코인을 잃어버리기 때문에(가중치가 있으니까) 데이크스트라로 풀어야하는것

 

이 문제는 데이크스트라 문제로 인접 칸으로 이동할때 비용을 더해서 최단 거리를 찾는문제이다.

다음에 갈 칸을 pq에 넣고 최단 거리의 경로를 다시 꺼내서 인접한 칸으로 계속해서 이동한다.

이후 최단 거리를 갱신할수 있는 경우에 갱신하고 큐에 추가해준다