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

알고리즘 문제에서 동적계획법과 함께 단골로 출시되는 것이 그래프 문제이다.

그래프 형태의 자료구조로 표현할 수 있는 문제를 해결하기 위한 알고리즘은 여러 가지가 있다.

그 중 가장 기본적이면서도 대표적인 알고리즘 기법이 넓이우선탐색(Breadth First Search)과 깊이우선탐색(Depth First Search)이다. 

이 중에서 먼저 넓이우선탐색(BFS, Breadth First Search)에 대해 그림으로 알아보고 예제 문제를 자바(java) 코드로 구현해 보자.

위와 같은 형태의 그래프가 있다. 이제 1번부터 시작해서 넓이우선탐색을 통해 모든 정점들을 하나씩 다 방문해 보려고 한다. 

넓이 우선 탐색은 처음 시작 정점을 방문한 뒤, 정점에서 인접한 모든 정점들을 우선 방문한다. 방문하지 않은 정점이 없어질 때까지 다른 모든 정점들에 대해서도 같은 방식으로 넓이 우선탐색을 수행한다.

넓이우선탐색은 선입선출 원칙으로 탐색을 해야 하기 때문에 Queue를 사용하게 된다.

연두색은 아직 방문하지 않은 정점, 회색은 예약되어 Queue에 넣어놓은 정점, 주황색은 이미 방문한 정점이다. 

[1] 1

가장 먼저 1번 노드에서 출발한다. 1번 노드와 인접한 노드인 2번과 3번을 Queue에 넣는다. 그 뒤 Queue의 맨 위에 있는 2번으로 이동하고 2번을 큐에서 뺀다.

[2] 1-2

이제 2번 노드와 인접한 노드인 4번 5번을 새로 큐에 넣어준다. 그 다음 큐의 맨 위에 있는 3번 정점으로 이동하면서 3번을 큐에서 뺀다.

[3] 1-2-3

이동한 3번 정점과 인접한 정점들인 6과 7을 큐에 넣어준다. 같은 방식으로 큐의 가장 위에 있는 4번을 빼고 4번으로 이동한다.

[4] 1-2-3-4

새로 이동한 4번 정점과 인접한 8번 정점을 큐에 넣는다. 역시 같은 방식으로 큐에서 5를 꺼내고 5번 정점으로 이동한다.

[5] 1-2-3-4-5

5번 정점으로 이동하고 보니 더이상 새롭게 추가할 인접한 정점은 없다. 새로 큐에 넣는 정점 없이 큐에서 가장 먼저 들어온 6번 정점을 빼고 6번으로 이동한다.

[6] 1-2-3-4-5-6

같은 방식으로 쭉 수행하면,

[7] 1-2-3-4-5-6-7

[8] 1-2-3-4-5-6-7-8

더이상 Queue에 남아있는 정점이 없을 때, 탐색을 종료한다. 모든 정점을 방문하여 주황색으로 변한 것을 확인할 수 있다. 넓이우선탐색은 빅오 O(V+E) 의 시간복잡도를 가진다.

아래는 넓이우선탐색를 사용해 java코드를 작성한 문제이다. 자바 코드에 주석으로 설명을 달았으니 참고하시면 된다.

---

문제

첫 번째 줄에 그래프의 정점의 개수 V, 간선의 개수 E, 그리고 시작 정점의 번호 S가 공백으로 분리되어 주어진다. (1 ≤ S ≤ V ≤ 20,000, 1 ≤ E ≤ 100,000)

두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보인 x, y가 공백으로 분리되어 주어진다. 이는 x와 y를 잇는 간선이 존재한다는 것을 의미한다. (1 ≤ x, y ≤ V, x ≠ y)

정점 S에서 시작한 너비 우선 탐색의 결과 중 오름차순으로 가장 빠른 것을 출력한다.

입력 예제

5 6 2
1 2
1 3
2 4
3 4
3 5
4 5

출력

2 1 4 3 5

---

코드

public class Bfs {
    static int V, E, S;
    static int x, y;
    static ArrayList<Integer> [] graph;
     
    static ArrayList<Integer> bfs;
     
    static boolean [] visit;  //이미 방문한 정점의 정보를 담을 배열
     
    static Queue<Integer> Q;
     
    static BufferedReader br;
    static BufferedWriter bw;
     
    static StringTokenizer st;
     
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
        st = new StringTokenizer(br.readLine());
         
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
         
        graph = new ArrayList[E+1];
        
        //각 정점의 간선으로 연결되어있는 정점들에 대한 정보를 담을 리스트를 초기화
        for (int i = 1; i <= E; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            
            //방향성이 없는 그래프이기 때문에 연결되는 양쪽에 서로에 대한 정보를 넣어줌
            graph[x].add(y);
            graph[y].add(x);
        }
         
        //연결된 간선 정보를 정렬
        for (int i=1; i<=E; i++){
            Collections.sort(graph[i]);
        }
         
        bfsSol();
        for (int i = 0; i < bfs.size(); i++) {
            System.out.print(bfs.get(i)+ " ");
        }
    }
     
    private static void bfsSol(){
        bfs = new ArrayList<Integer>();
        visit = new boolean [E +1];
        Q = new LinkedList<Integer>();
        
        //시작정점을 큐에 넣어줌
        Q.add(S);
        //시작정점을 방문했다는 정보 저장
        visit[S] = true;
        
        //큐에 정점이 없어질 때까지 반복
        while(!Q.isEmpty()){
            //큐에서 정점을 poll해서 이동함
            int q = Q.poll();
            bfs.add(q);
            //이동한 정점에서 연결된 정점들을 큐에 넣어주고 visit배열에 체크
            for(int i : graph[q]){
                if(!visit[i]){
                    Q.add(i);
                    visit[i] = true;
                }
            }
        }
         
    }
}