[백준] 24444번 알고리즘 수업 - 너비 우선 탐색 1 JAVA (자바) 풀이

문제 24444번 (bfs)

 :  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를 추가한다.
            }
    }
}

 

 

 [입력]

 :  첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)

 :  다음 M개 줄에 간선 정보 u v (가중치 1인 양방향 간선) (1 ≤ u < v ≤ N, u ≠ v)
    모든 간선의 (u, v) 쌍의 값은 서로 다르다

 

 

[출력]

 :  첫째 줄부터 N개의 줄에 방문 순서를 출력 (시작 정점에서 방문할 수 없는 경우 0을 출력)    

 

[설명]

 

1. count를 통해 인덱스 추출

 

2. 오름차순 Collections.sort() 사용할 것

• for(){ bfs } 하지말 것 (bfs 메서드 내에서 큐에 계속 추가하면서 반복하면 된다)
• bfs메서드 내에서 다시 bfs를 호출하지 말 것 (백트래킹이나 dfs와는 다르다)

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static boolean visit[];
    static int N,M,R,u,v,result[];
    static ArrayList<Integer> arr[];
    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());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        arr=new ArrayList[N+1];
        visit = new boolean[N+1];
        result = new int[N+1];
        
        for(int i=1; i<=N; i++){
            arr[i]=new ArrayList<>();
        }
        
        while(M-->0){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            arr[u].add(v);
            arr[v].add(u);
        }
        
        for(int i=1; i<=N; i++){
            Collections.sort(arr[i]);
        }
       
        bfs(R);
        
        for(int i=1; i<=N; i++){
            System.out.println(result[i]);
        }
    }
    
    static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visit[start]=true;
        result[start]=count++;
        
        while(!q.isEmpty()){
            int p = q.poll();
            for(int i=0; i<arr[p].size();i++){
                int next = arr[p].get(i);
                if(!visit[next]){
                    q.add(next);
                    visit[next]=true;
                    result[next]=count++;
                }
            }
        }
    }
}

 

 [해설]
     

 :  static boolean visit[];
    static int N,M,R,u,v,result[];
    static ArrayList<Integer> arr[];
    static int count =1;  count를 1로 초기화
   

 :  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());
    arr=new ArrayList[N+1];
    visit = new boolean[N+1];
    result = new int[N+1];
        
 :  for(int i=1; i<=N; i++){
          arr[i]=new ArrayList<>();
    }
        
 :  while(M-->0){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            arr[u].add(v);  양방향이라 양쪽으로 추가
            arr[v].add(u);  양방향이라 양쪽으로 추가
    }
       

 :  for(int i=1; i<=N; i++){
            Collections.sort(arr[i]);  오름차순 정렬
    }
       
 :  bfs(R);  시작 정점에서 bfs 돌리기
        
 :  for(int i=1; i<=N; i++){
            System.out.println(result[i]);  result 배열 출력
    }
    
    
 :  static void bfs(int start){  
        Queue<Integer> q = new LinkedList<>();  큐 선언
        q.add(start);  큐에 시작 노드 추가
        visit[start]=true;  시작노드 방문
        result[start]=count++;  count 추가
        
        while(!q.isEmpty()){
            int p = q.poll();  큐에서 뽑기
            for(int i=0; i<arr[p].size();i++){  연결된 노드 개수만큼 반복
                int next = arr[p].get(i);  연결된 노드들 뽑기
                if(!visit[next]){  방문하지 않았으면
                    q.add(next);  큐에 추가
                    visit[next]=true;  방문처리
                    result[next]=count++;  count 증가
                }
            }
        }
   }



   

 

      

이제 풀어보러 갈께요 :)

 

 

https://www.acmicpc.net/problem/24444

 

 

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *