BFS 알고리즘

 

너비 우선 탐색(BFS, Breadth-First Search)

너비 우선 탐색이란?

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

 

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
  즉, 
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
  - Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
  - 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
  - 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

 

 

 

너비 우선 탐색(BFS)의 특징

• 직관적이지 않은 면이 있다.
  - BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
• BFS는 재귀적으로 동작하지 않는다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
  - 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
  - 즉, 선입선출(FIFO) 원칙으로 탐색
  - 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
• ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.
  
  

 

 

 

 

 

 

 

 

 

예시

---

프로그래머스 - 경주로 건설

 

 

import java.util.*;

class Solution {
    static int[][][] dp;
    static int[] dx = {0,-1,1,0}; 
    static int[] dy = {-1,0,0,1};
    static int N;
    static int answer;
    
    public int solution(int[][] board) {
        answer = Integer.MAX_VALUE;
        N = board.length;
        dp = new int[N][N][4];
            
        for(int i=0; i<N; i++) 
            for (int j=0; j<N; j++) 
                for(int k=0; k<4; k++) 
                    dp[i][j][k] = Integer.MAX_VALUE;                
        
        dp[0][0][0] = 0;
        dp[0][0][1] = 0;
        dp[0][0][2] = 0;
        dp[0][0][3] = 0;        

        bfs(0,0, board);    
        
        return answer;
    }
    
    private void bfs(int x, int y, int[][] board) {
        Deque<int[]> deque = new ArrayDeque<>();
        deque.add(new int[]{x, y, 0});
        
        while(!deque.isEmpty()) {
            int[] pos = deque.poll();
            x = pos[0]; y = pos[1];
            int preDir = pos[2];
            
            for(int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if(board[nx][ny] == 1) continue;
                
                int newCost = dp[x][y][preDir];
                if ((x == 0 && y == 0) || i == preDir) { 
                    newCost += 100;
                } else {
                    newCost += 600;
                }
                
                if(dp[nx][ny][i] >= newCost) {
                    dp[nx][ny][i] = newCost;
                    deque.add(new int[]{nx, ny, i});
                    if(nx == N-1 && ny == N-1) {
                        answer = Math.min(newCost, answer);
                    }
                }
            }            
        }        
    }
}

 

 

 

---

프로그래머스 - 게임 맵 최단거리

-> 성공

-> 노드마다 점수가 있는 게 아닌 이상 최단 거리를 구할 때는 효율이 매우 좋다.

 

 

import java.util.*;

class Solution {
    int[][] direction = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    boolean[][] visited;
    int[][] score;
    
    public int solution(int[][] maps) {
        visited = new boolean[maps.length][maps[0].length];
        score = new int[maps.length][maps[0].length];
        
        bfs(maps);
        if(score[score.length-1][score[0].length-1] == 0) {
            return -1;
        }
        
        return score[score.length-1][score[0].length-1];
    }
    
    public void bfs(int[][] maps) {
        int x = 0;
        int y = 0;
        visited[x][y] = true;
        score[x][y] = 1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        
        while(!q.isEmpty()) {
            int[] cur = q.remove();
            int cx = cur[0];
            int cy = cur[1];
            
            for(int i=0; i<4; i++) {
                int nx = cx + direction[i][0];
                int ny = cy + direction[i][1];
                
                if(nx < 0 || nx > maps.length-1 || ny < 0 || ny > maps[0].length-1) {
                    continue;
                }
                
                if(visited[nx][ny] == false && maps[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                    score[nx][ny] = score[cx][cy] + 1;
                }
            }
        }
    }
}

 

 

---

프로그래머스 - 가장 먼 노드

 

 

 

import java.util.*;

class Solution {
    boolean[] visited;
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        visited = new boolean[n+1];
        return bfs(edge);
    }
    
    public int bfs(int[][] edge) {
        int answer = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {1,0});
        visited[1] = true;
        int maxDepth = 0;
        
        while(!q.isEmpty()) {
            int[] tmp = q.remove();           
            int depth = tmp[1];
            
            if(maxDepth ==  depth) {
                answer++;
            }
            if(maxDepth < depth) {
                maxDepth = depth;
                answer = 1;
            }
            
            for(int i=0; i<edge.length; i++) {
                if(edge[i][0] == tmp[0]) {
                    if(visited[edge[i][1]] == false) {
                        q.add(new int[] {edge[i][1], depth+1});    
                        visited[edge[i][1]] = true;
                    }
                }
                if(edge[i][1] == tmp[0]) {
                    if(visited[edge[i][0]] == false) {
                        q.add(new int[] {edge[i][0], depth+1});    
                        visited[edge[i][0]] = true;
                    }                    
                }
            }
        }
        return answer;
    }
}