글 읽기 - BFS에 대한 개념이 부족하여 질문드립니다.

abcd1428 3년 전 0

안녕하세요

아래 소스는 맞는 소스입니다. 제가 궁금한점은 만들때 bfs로 풀어야지 라고 생각하고 만들었는데요

다익스트라 문제는 bfs로 풀면 정답을 보장할수가 없다라고 하는데

아래소스는 bfs가 아닌건가요? 개념이 부족하여 질문 드립니다.

if(node.get(i)[my][mx][1] > cost + node.get(i)[my][mx][0]) 이 조건으로 인하여 bfs가 아닌건지,

visit 방문체크를 안했기 때문에 bfs가 아닌건지 궁금합니다.

선배님들 시간내주셔서 감사합니다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        ArrayList<int[][][]> node = new ArrayList<>();
        while (true) {
            int count = Integer.parseInt(bf.readLine());
            if(count == 0) break;
            node.add(new int[count][count][2]);
            for(int i=0; i<count; i++) {
                String[] input = bf.readLine().split(" ");
                for(int j=0; j<count; j++) {
                    node.get(node.size()-1)[i][j][0] = Integer.parseInt(input[j]);
                    node.get(node.size()-1)[i][j][1] = 100000000;
                }
            }
        }

        Queue<int[]> qu = new LinkedList<>();
        for(int i=0; i<node.size(); i++) {
            int length = node.get(i).length;

            node.get(i)[0][0][1] = node.get(i)[0][0][0];
            qu.add(new int[]{0, 0, node.get(i)[0][0][1]});
            while (!qu.isEmpty()) {
                int[] yx = qu.poll();
                int y = yx[0];
                int x = yx[1];
                int cost = yx[2];
                for(int j=0; j<4; j++) {
                    int my = y+ly[j];
                    int mx = x+lx[j];
                    if(chk(my, mx, length)) {
                        if(node.get(i)[my][mx][1] > cost + node.get(i)[my][mx][0]) {
                            node.get(i)[my][mx][1] = cost + node.get(i)[my][mx][0];
                            qu.add(new int[]{my, mx, cost + node.get(i)[my][mx][0]});
                        }
                    }
                }
            }
        }

        for(int i=0; i<node.size(); i++) {
            System.out.println("Problem " + (i+1) + ": " +node.get(i)[node.get(i).length-1][node.get(i).length-1][1]);
        }
    }

    static int[] ly = {-1,0,1,0}; //위 오 아 왼
    static int[] lx = {0,1,0,-1};

    static boolean chk(int y, int x, int max) {
        if(y < 0 || y >= max || x < 0 || x >= max) {
            return false;
        } else {
            return true;
        }
    }
}

min61037 2년 전 1

지금쯤이면 고민이 해결되셨을 수도 있지만 혹시나 하여 올립니다.

bfs는 시작점에서부터 동일한 거리를 짧은 순서대로 탐색합니다.

거리가 1인 곳, 거리가 2인 곳, 거리가 3인 곳 이렇게 촘촘히 검사하지요. 따라서 거리가 3인 곳을 방문할 땐 거리가 2인 곳에서 다시 거리가 1인 곳으로 가지 않습니다.

왔던 곳을 다시 가지 않는다는 말입니다.

그러나 다익스트라는 왔던 곳을 다시 가기도 합니다. 왔던 곳을 방문하는 더 빠른 최단경로가 존재한다면 말이지요.

따라서 알고리즘의 목적 자체가 다른 겁니다. bfs는 모든 곳을 둘러보는 알고리즘이며 다익스트라는 모든 곳에 대해서 방문하는 최단 경로를 알아내는 알고리즘입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

BFS에 대한 개념이 부족하여 질문드립니다.

abcd1428 3년 전 0

min61037 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말