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

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

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

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

- 정점 번호는 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를 추가한다.
            }
    }
}

 

 

문제 풀이 

 

- N: 정점의 수 

- M : 간선의 수 

- R :시작 정점 

 

- 2차원의 boolean 배열로 그래프 표현 

 

BFS의 특징 

[Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현 (tistory.com)

[Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현

 

- BFS는 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색한다. 

- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 

- BFS는 재귀적으로 동작하지 않는다. 

- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)를 사용한다. 

- 즉, 선입선출(FIFO) 원칙으로 탐색 

- 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

 

 

1) 시작 노드를 방문한다 . (방문한 노드 체크)

  - 큐에 방문된 노드를 삽입한다.(enqueue)

  - 초기 상태의 큐에는 시작 노드만이 저장된다. 

 

 2) 큐에서 꺼낸 노드와 인접한 노드들을 큐에 추가한다. (모두 차례로 방문)

  - 큐에서 꺼낸 노드를 방문한다.   

  - 큐에서 꺼낸 노드과 인접한 노드들을 모두 방문한다. 

  - 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다. (dequeue)

  - 큐에 방문한 노드를 삽입한다.(enqueue)

 

 3)  큐가 공백 상태가 될 떄까지 계속한다. 

 

 

인접 리스트로 구현

 

 

문제 풀이 

 

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]); //방문 순서를 위해 오름차순 정렬
        }
        
        bfs(R,list,visited);

    }
}