그래프의 탐색_BFS

Algorithm : 그래프의 탐색_BFS

BFS

: Breadth-First-Search, 시작 정점으로부터 가장 가까운 정점을 먼저 방문하고, 멀리 떨어져있는 정점을 나중에 방문한다. 루트 노드나 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

 

BFS의 특징

• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
• 큐를 이용해 반복적 형태로 구현한다.
• 노드 방문 여부를 확인해야 한다. 그렇지 않을 경우 무한 루프에 빠질 위험이 있다.

 

BFS의 구현

인접 리스트를 이용한 구현

import java.util.ArrayList;

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

public class Main {

	static int V, S; // V는 정점의 개수, S는 탐색을 시작할 정점 번호
	static int x, y; // x와 y 사이의 경로가 존재
	static ArrayList<ArrayList<Integer>> graph;
	static ArrayList<Integer> bfs;
	static boolean[] visited;
	static Queue<Integer> queue;

	public static void bfs() {

		bfs = new ArrayList<Integer>();
		visited = new boolean[V + 1];
		queue = new LinkedList<Integer>();

		queue.offer(S);
		visited[S] = true;
		
		while(!queue.isEmpty()) {
			int q = queue.poll();
			bfs.add(q);

			for(int i : graph.get(i)) {
				if(!visited[i]) {
					queue.offer(i);
					visited[i] = true;
				}
			}

		}
		
	}

	public static void main(String[] args) {
		
		// V, S initial

		graph = new ArrayList<ArrayList<Integer>>();

		for(int i = 0; i < V+1; i++)
			graph.get(i).add(new ArrayList<Integer>());

		for(int i = 0; i < V+ 1; i++) {
		    // input x, y
		    
			graph.get(x).add(y);
			graph.get(y).add(x);
		} // 양방향 추가

		bfs();

		for(int i = 0; i < bfs.size(); i++)
			System.out.println(bfs.get(i) + " ");

	}

}

 

BFS 알고리즘 코드

출처 : 2667번: 단지번호붙이기 (acmicpc.net)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;

class Dot {
    
    int x;
    int y;
    
    public Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
}

public class Main {
    
    public static int N;
    public static int[][] map;
    public static boolean[][] visited;
    public static ArrayList<Integer> answer;
    
    public static Queue<Dot> queue;
    
    public static int[] rowArr = {-1, 0, 1, 0};
    public static int[] colArr = {0, -1, 0, 1};
    
    public static void bfs(int i, int j) {
        
        queue.offer(new Dot(i, j));
        
        int count = 1;
        
        while(!queue.isEmpty()) {
            
            Dot dot = queue.poll();
            visited[dot.x][dot.y] = true;
            
            for(int k = 0; k < 4; k++) {
                
                int row = dot.x + rowArr[k];
                int col = dot.y + colArr[k];
                
                if(checkDot(row, col)) {
                    count += 1;
                    map[row][col] = count;
                    queue.add(new Dot(row, col));
                }
                
            }
            
        }
        
        answer.add(count);
        
    }
    
    public static boolean checkDot(int row, int col) {
        
        if(row >= N || col >= N || row < 0 || col < 0)
            return false;
        if(map[row][col] != 1 || visited[row][col] == true)
            return false;
            
        return true;
        
    }
    
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		visited = new boolean[N][N];
		answer = new ArrayList<Integer>();
		queue = new LinkedList<Dot>();
		
		for(int i = 0; i < N; i++) {
		    String line = br.readLine();
		    for(int j = 0; j < N; j++)
		        map[i][j] = line.charAt(j) - '0';
		}
		
		for(int i = 0; i < N; i++)
		    for(int j = 0; j < N; j++)
		        if(map[i][j] == 1 && visited[i][j] == false)
        		    bfs(i, j);
		            
		
		Collections.sort(answer);
		
		StringBuilder sb = new StringBuilder();
		
		sb.append(answer.size()).append("\n");
		
		for(int i = 0; i < answer.size(); i++)
		    sb.append(answer.get(i)).append("\n");
		
		System.out.println(sb);
	}
}

 

---

 

BFS 참고 사이트

• 그래프 넓이우선탐색(BFS, Breadth First Search) 알고리즘(java 코드 포함) (leafcats.com)