[BaekJoon] #24445 알고리즘 수업 - 너비 우선 탐색 2

문제 이해

너비 우선 탐색 1 문제와 완전 동일합니다.

앞의 문제는 인접 정점을 오름차순으로 정렬 한 후에 방문하는거였는데, 이 문제는 내림차순으로 정렬하면 됩니다.

Collections.reverseOrder() 옵션만 넣어주면 됩니다 짱쉬움 !

그래프 구현

앞의 포스팅에서 이미 구현했지만 외울 겸 한번 더 설명하겠습니다.

BFS 방법으로 탐색하려면, 탐색하려는 그래프 먼저 생성해야 합니다.

그래프를 표현하기 위해 인접행렬이나 인접리스트를 사용할 수 있습니다.

BFS를 할 땐, 너비 우선 탐색이기 때문에 각 정점에 연결된 인접 정점들을 담은 리스트들을 순서대로 탐색합니다.

이 순서를 오름차순으로 할 수도 있고, 이 문제처럼 내림차순으로 설정할 수 있습니다.

또한, 무방향 그래프이므로 대칭적으로 저장하게 되어 인접 정점들은 중복이 됩니다.

중복탐색을 방지하기 위해, 방문한 노드인지 판별하는 visited[] 를 생성해주어야 합니다.

그래프 code

BFS code

아래와 같이 작성해주면 됩니다.

code

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

public class Main{
    static int result[];
    static int count =1;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        LinkedList<Integer>[] adjList = new LinkedList[n+1];  // 인접리스트 객체 생성
        boolean[] visited = new boolean[n+1]; // 정점 방문 기록용 배열
        result = new int[n+1]; // 결과 출력용 배열

        for(int i=0; i<=n; i++){
            adjList[i] =  new LinkedList<Integer>();
        } // 각 정점에 대한 인접 정점을 저장할 리스트

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            adjList[v1].add(v2);
            adjList[v2].add(v1);
        } // 정점 추가 _ 무방향그래프이므로, 양방향 넣어주기

        for(int i=0; i<=n; i++){
            Collections.sort(adjList[i], Collections.reverseOrder());
        }
        BFS(v,adjList,visited);
        for(int i=1;i<=n; i++) {
            System.out.println(result[i]);
        }
    }

    static void BFS(int v,  LinkedList<Integer>[] adjList, boolean[] visited){
        Queue<Integer> queue = new LinkedList<Integer>();
        visited[v] = true;
        queue.add(v);

        result[v] = count++;

        while(!queue.isEmpty()){
            v = queue.poll();
            //System.out.println(v);


            Iterator<Integer> iter = adjList[v].listIterator();
            while(iter.hasNext()){
                int w = iter.next();
                if(!visited[w]){
                    queue.add(w);
                    visited[w]=true;
                    result[w] = count ++;
                }
            }
        }
    }
}