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

📖 문제

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

 

 

💡  풀이 방식

• BFS + 정렬

1. ArrayList 배열을 만들어 양방향 그래프를 만든다.

2. ArrayList 배열의 각 ArrayList를 오름차순 정렬한다.

3. BFS를 하면서 방문하지 않은 노드를 방문 처리하고 순서를 기록한다.

4. 1~M까지 순서대로 정점들의 방문한 순서 출력

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, R;
    static ArrayList<Integer>[] A;
    static int[] visited;
    
    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());
        
        A  = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        visited = new int[N + 1];
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
        
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            A[u].add(v);
            A[v].add(u);
        }
        
        // 방문 정점 오름차순 ㅓㅇ렬
        for(int i = 1 ; i <= N ; i++) {
            Collections.sort(A[i]);
        }
        
        bfs(R);
        
        // 순서대로 방문 순서 출력
        for(int i = 1 ; i <= N ; i++) {
            System.out.println(visited[i]);
        }
    }
    
    private static void bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        int cnt = 1;    // 방문 순서 변수
        
        q.offer(x);
        visited[x] = cnt++;    // 시작 노드 방문 처리
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int next : A[now]) {    // 해당 노드와 연결된 노드 순회
                if(visited[next] != 0)   continue;
                
                q.offer(next);
                visited[next] = cnt++;
            }
        }
    }
}
 

 

---

💦 어려웠던 점

- 방문 순서를 어떻게 기록할지 어떤 변수를 사용할지 고민을 하였다.

 

🧐 새로 알게 된 내용

- BFS를 할 때마다 방문 순서를 나타내는 변수 cnt를 +1하면 되는 것이었다..

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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