[JAVA] 백준 24445 알고리즘 수업 - 너비 우선 탐색 2

24445번: 알고리즘 수업 - 너비 우선 탐색 2 (acmicpc.net)

24445번: 알고리즘 수업 - 너비 우선 탐색 2

 

 

- N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 

- 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자 

 

-너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차순으로 방문한다.

 

bfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    for each v ∈ V - {R}
        visited[v] <- NO;
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    enqueue(Q, R);  # 큐 맨 뒤에 시작 정점 R을 추가한다.
    while (Q ≠ ∅) {
        u <- dequeue(Q);  # 큐 맨 앞쪽의 요소를 삭제한다.
        for each v ∈ E(u)  # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 내림차순으로 방문한다)
            if (visited[v] = NO) then {
                visited[v] <- YES;  # 정점 v를 방문 했다고 표시한다.
                enqueue(Q, v);  # 큐 맨 뒤에 정점 v를 추가한다.
            }
    }
}

 

 

정답 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class Main {
    static boolean visited[];
    static int N,M,R;
    
    //bfs
    public static void bfs(int r, LinkedList<Integer>[] list, boolean visited[])
    {
    	int order[] = new int[N+1]; //긱 정점의 방문 순서 기록
    	Queue<Integer>q = new LinkedList<Integer>();
    	visited[r] = true;
    	q.add(r); //시작 정점 큐에 추가 
    	int count=1; //방문 순서를 기록
    	
    	while(q.size()!=0)
    	{
    		r = q.poll();
    		order[r] = count++; //정점 r의 방문 순서를 기록
    		
    		Iterator<Integer> iter = list[r].listIterator();
    		
    		while(iter.hasNext()) {
    			int w = iter.next();
    			if(!visited[w]) {
    				visited[w] = true;
    				q.add(w);
    			}
    		}
    	}
    	//각 정점의 방문 순서를 출력
    	for(int i=1; i<=N; i++)
    	{
    		System.out.println(order[i]);
    	}
    	
    	
    }
    
    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()); //시작 정점
        
        LinkedList<Integer>[] list = new LinkedList[N+1];
        visited = new boolean[N+1]; //방문여부 검사 
        
        
        for(int i=0; i<=N; i++)
        {
        	list[i] = new LinkedList<Integer>();
        }
        
        for(int i=0; i<M; i++)
        {
        	st = new StringTokenizer(br.readLine());
        	int x = Integer.parseInt(st.nextToken());
        	int y = Integer.parseInt(st.nextToken());
        	list[x].add(y);
        	list[y].add(x);
        }
        
        for(int i=1; i<=N; i++)
        {
        	Collections.sort(list[i], Collections.reverseOrder()); //방문 순서를 위해 내림차순 정렬
        }
        
        bfs(R,list,visited);

    }
}