[알고리즘] BFS - 큐, 최단거리

1. Queue 사용

 

import org.springframework.boot.autoconfigure.SpringBootApplication;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

@SpringBootApplication
public class Main {

    static final int Max_N = 10;
    static int N, E;
    static int[][] Graph = new int [Max_N][Max_N]; // 노드,간선 정보를 이중배열에 담아둠
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<E; i++){
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            Graph[u][v] = Graph[v][u] = 1;
        }

        bfs(0); // 시작노드 0

    }

    public static void bfs(int node){
        boolean[] visited = new boolean[Max_N];

        Queue<Integer> myqueue = new LinkedList<>(); // 선입선출
        visited[node] = true; // 첫번째 노드를 방문했다고 치고 true
        myqueue.add(node);

        while (!myqueue.isEmpty()) {
            int curr = myqueue.remove();
            System.out.print(curr+" "); // 실제 방문은 여기서

            for(int next=0; next<N; next++){
                if(!visited[next] && Graph[curr][next]!=0){ // 다음노드가 방문하지 않았던 노드이고, 현재노드-다음노드 사이에 간선이 존재한다면
                    visited[next] = true;
                    myqueue.add(next);
                }
            }
        }


    }

}

 

 

2. 최단거리 구하기

import org.springframework.boot.autoconfigure.SpringBootApplication;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

@SpringBootApplication
public class Main {

    static final int Max_N = 10;
    static int[][] D = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int N;
    static int[][] Board = new int [Max_N][Max_N]; // 노드,간선 정보를 이중배열에 담아둠
    static class Point {
        int row, col, dist;
        Point(int r, int c, int d) {
            row = r; col = c; dist = d;
        }
    }
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        for(int i=0; i<N; i++){ // Board 에 위치정보를 담아둠
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                Board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        int sRow, sCol, dRow, dCol;
        sRow = Integer.parseInt(st.nextToken());
        sCol = Integer.parseInt(st.nextToken());
        dRow = Integer.parseInt(st.nextToken());
        dCol = Integer.parseInt(st.nextToken());
        // 시작 및 도착 위치로 bfs 메소드 실행
        System.out.println(bfs(sRow, sCol, dRow, dCol));


    }

    static int bfs(int sRow, int sCol, int dRow, int dCol){
        boolean[][] visited = new boolean[Max_N][Max_N];
        Queue<Point> myqueue = new LinkedList<>();
        visited[sRow][sCol] = true; // 방문한 노드는 true
        myqueue.add(new Point(sRow, sCol, 0)); // 처음에 dist 는 0

        while (!myqueue.isEmpty()) {
            Point curr = myqueue.remove();
        //    System.out.println(curr.row+", "+curr.col);
            if (curr.row == dRow && curr.col == dCol) {// 도착한다면 리턴
                return curr.dist; // 도착후 여기서 리턴하게됨
            }

            for(int i=0; i<4; i++){
                int nr = curr.row + D[i][0], nc = curr.col + D[i][1];
                if(nr < 0 || nr > N-1 || nc < 0 || nc > N-1) continue;
                if(visited[nr][nc]) continue;
                if(Board[nr][nc] ==1 )continue;
                visited[nr][nc] = true;
                myqueue.add(new Point(nr, nc, curr.dist + 1));
            }
        }

        return -1;

    }

}

 

출처 : https://www.youtube.com/watch?v=yQ7o1Y7X_Rg&t=11s