BFS 공부 - 최단 거리 (최소 시간)

★BFS는 Queue 자료구조 사용

: 먼저 온 사람이 먼저 나간다 (First In, First Out)

 

★BFS 실전 뼈대 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution{
	static boolean[] visited;
    
    public void bfs(int startNode, int[][] graph, int n){
    	// 대기 명단을 준비한다
        Queue<Integer> queue = new LinkedList<>();
        
        // 시작점을 큐에 넣고 방문 도장을 찍는다
        queue.add(startNode);
        visited[startNode] = true;
        
        // 대기명단이 텅 빌 때까지 무한 반복
        while(!queue.isEmpty()){
        	// 대기 명단 맨 앞줄에 있는 사람을 꺼낸다
            int current = queue.poll();
            
            // 꺼낸 사람의 이웃들을 전부 살펴본다
            for(int nextNode = 1; nextNode <= n; nextNode++){
            	// 연결되어있고 한번도 방문 안한 친구라면?
                if(graph[current][nextNode]==1 && !visited[nextNode]){
                	// 대기 명단 맨 뒤에 줄을 세우고 방문 도장 찍는다
                    queue.add(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
    }
}

 

★ 2차원 배열 격자판에서의 상하좌우

// 상하좌우 순서대로 x와 y의 변화량
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};

// for문을 4번 돌리면서 현재 좌표 (x,y)에 더해주면 사방 찔러보기 가능
for(int i=0; i<4; i++){
	int nx = currentX + dx[i];
    int ny = currentY + dy[i];
}

 

★ Queue에 좌표 두개(x,y)를 같이 넣는 법

class Node{
	int x, y, cost;
    
    Node(int x, int y, int cost){
    	this.x = x;
        this.y = y;
        this.cost = cost;
    }
}

Queue<Node> q = new LinkedList<>();
q.add(new Node(0, 0, 1)); // 0,0 좌표에서 시작 거리 1로 출발