백준 No.24444 알고리즘 수업 - 너비 우선 탐색 1 - JAVA

 

 

문제

오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다 정점 번호는 1번부터 N 번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색을 노드를 방문할 경우 노드의 방문 순서를 출력하자

인접 정점은 오름차순으로 방문한다.

 

 

풀이

1. Queue를 생성한다.

2. Queue에 시작 노드 번호를 add 한다.

3. visited 배열에도 시작노드를 방문처리한다.

4. result배열을 만든다. --> 인덱스가 각 노드이고 순서를 지정한다. (3번 인덱스에 4가 들어가면 3번 노드는 4번째로 방문한다는 뜻임)

5. while(!queue.isEmpty())

6. int now = queue.poll() --> 현재 탐색을 하기 전 위치한 노드

7. for(int i=0;i<graph.get(now).size();i++)   -->> 인접 리스트이기때문에 해당 인덱스에 있는 리스트(해당 노드와 연결된 노드) 들 크기만큼 for문을 순회하기에 0부터 크기까지면 된다.

8. if(!visited[graph.get(now).get(i)])  --> 다음 노드들을 방문하지 않았다면 방문처리하고 queue에 추가한다. 이 과정에서 방문을 한 것이기에 순서를 정할 수 있다. 맨 처음에 result배열을 만들었으므로 그 배열에 1씩 추가해서 넣으면 된다.

이런식으로 구성 만약 3번 노드를 4번째로 방문한다는 가정하에 본다면 next에는 3이 들어가고 count는 4가 들어갈 것이다. 

 

 

 

코드

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

public class Main {

    static int N,M,R;
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    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());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());


        visited = new boolean[N+1];
        for(int i = 0;i<N;i++){
            graph.add(new ArrayList<>());
        }

        for(int i =0;i<M;i++){
            st =  new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph.get(start).add(end);
            graph.get(end).add(start);
        }
        for(int i =1;i<N;i++){
                Collections.sort(graph.get(i));
        }

        BVFS(R);
    }

    private static void BVFS(int r) {
        Queue<Integer> queue = new LinkedList<>();
        int count = 0;
        int result[] = new int[N+1];
        queue.add(r);
        visited[r] = true;
        result[r] = ++count;

        while(!queue.isEmpty()){
            int now = queue.poll();

            for(int i = 0 ; i< graph.get(now).size();i++){
                    int next = graph.get(now).get(i);
                    if(!visited[next]){
                            queue.add(next);
                            visited[next] = true;
                        result[next] = ++count;
                    }
            }

        }
        for(int i=1;i<result.length;i++) System.out.println(result[i]);

    }
}