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

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

 

알고리즘의 기본이라고 알고있는 DFS, BFS 중 BFS 문제를 풀어보았다.

 

이 문제를 풀면서 필수적이라고 생각했던 부분

1. 방문여부를 기억하는 것

2. 양방향 간선이기 때문에 '시작정점의 리스트에 끝정점을 추가'하고 반대로 '끝정점의 리스트에 시작정점을 추가'

3. 방문순서를 기억하는 배열의 인덱스가 곧 정점이다.

- 방문이동횟수를 카운트 하여 몇번 정점에 몇번째로 방문했는지 데이터 삽입.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++){
            graph.add(new ArrayList<>()); // 각 정점에 대해 빈 리스트를 추가하여 그래프의 인접 리스트를 초기화합니다.
        }

        for (int i=0; i< M; i++){ // M 개의 간선을 입력받아 그래프에 추가
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v); // 시작 정점 u의 리스트에 끝 정점 v를 추가한다.
            graph.get(v).add(u); // 끝 정점 v의 리스트에 시작 정점 u를 추가한다.
        }

        for(int i=1; i<=N; i++){
            Collections.sort(graph.get(i)); // 각 정점의 인접 리스트를 오름차순으로 정렬
        }

        boolean[] visited = new boolean[N+1]; // 방문 여부를 저장하는 배열 // 정점 번호가 1부터 시작하므로 크기는 N+1
        int[] order = new int[N+1]; // 방문 순서를 기록할 배열, 초기값은 0 // order의 인덱스를 node로 가정
        Queue<Integer> q = new LinkedList<>(); // BFS 탐색을 위한 큐

        q.add(R); // 시작 정점 R을 큐에 추가한다.
        visited[R] = true; // 시작 정점 R을 방문했음을 표시

        int visitOrder = 1; // 첫번째 방문이기 때문에 1로 시작
        order[R] = visitOrder++; // 첫번째 방문(1)이후 visitOrder 2로 세팅

        while(!q.isEmpty()){
            int node = q.poll();

            for(int next : graph.get(node)) { // 현재 정점에 인접한 모든 정점을 탐색
                if(!visited[next]){
                    visited[next] = true;
                    q.add(next);
                    order[next] = visitOrder++; // 방문 후 visitOrder 1씩 추가 //방문 순서를 ++해가면서 순서를 설정

                }
            }
        }

        // 방문한 정점을 출력 // order의 인덱스가 정점. 해당 정점을 몇번째에 방문했는지가 출력값
        for (int i=1; i<=N; i++) { // 5번 인덱스 까지 있기 때문에 '<='이다.
            if(i==N){
                bw.write(String.valueOf(order[i]));
            } else {
                bw.write(order[i] + "\n");
            }
        }
        bw.flush();
    }
}

 

코드 실행 과정

1. 그래프 초기화

- 'graph' 리스트를 생성하고 각 정점에 대해 빈 리스트를 추가

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
    graph.add(new ArrayList<>());
}

 

2. 간선 입력

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    graph.get(u).add(v);
    graph.get(v).add(u);
}

 

- 간선 입력 후 'graph' 리스트

graph[0] = []
graph[1] = [4, 2]
graph[2] = [3, 4, 1]
graph[3] = [4, 2]
graph[4] = [1, 2, 3]
graph[5] = []

 

3. 그래프 정렬

for (int i = 1; i <= N; i++) {
    Collections.sort(graph.get(i));
}

 

- 그래프 정렬 후 'graph' 리스트

graph[0] = []
graph[1] = [2, 4]
graph[2] = [1, 3, 4]
graph[3] = [2, 4]
graph[4] = [1, 2, 3]
graph[5] = []

 

4. BFS 탐색 초기화

boolean[] visited = new boolean[N + 1];
int[] order = new int[N + 1];
Queue<Integer> q = new LinkedList<>();

q.add(R);
visited[R] = true;

int visitOrder = 1;
order[R] = visitOrder++;

 

- 초기상태

visited = [false, true, false, false, false, false]
order = [0, 1, 0, 0, 0, 0]
q = [1]
visitOrder = 2

 

5. BFS 탐색과정

- BFS 탐색을 진행하면서 큐가 비어있지 않을 때까지 다음을 반복

while (!q.isEmpty()) {
    int node = q.poll();
    for (int next : graph.get(node)) {
        if (!visited[next]) {
            visited[next] = true;
            q.add(next);
            order[next] = visitOrder++;
        }
    }
}

 

정점 1 방문

• node = q.poll() 결과: node = 1
• graph.get(1) 결과: [2, 4]
• 방문 상태:

visited = [false, true, true, false, true, false]
order = [0, 1, 2, 0, 3, 0]
q = [2, 4]
visitOrder = 4

 

정점 2 방문

• node = q.poll() 결과: node = 2
• graph.get(2) 결과: [1, 3, 4]
• 정점 1은 이미 방문됨, 정점 4도 이미 방문됨, 정점 3은 방문되지 않음
• 방문 상태:

visited = [false, true, true, true, true, false]
order = [0, 1, 2, 4, 3, 0]
q = [4, 3]
visitOrder = 5

 

정점 4 방문

• node = q.poll() 결과: node = 4
• graph.get(4) 결과: [1, 2, 3]
• 모두 이미 방문됨
• 방문 상태는 변하지 않음:

visited = [false, true, true, true, true, false]
order = [0, 1, 2, 4, 3, 0]
q = [3]
visitOrder = 5

 

정점 3 방문

• node = q.poll() 결과: node = 3
• graph.get(3) 결과: [2, 4]
• 모두 이미 방문됨
• 방문 상태는 변하지 않음:

visited = [false, true, true, true, true, false]
order = [0, 1, 2, 4, 3, 0]
q = []
visitOrder = 5

 

6. 결과출력

- order 배열을 순회하며 방문 순서를 출력

for (int i=1; i<=N; i++) {
    if(i==N){
        bw.write(String.valueOf(order[i])); // 마지막 순서 줄바꿈 제거
    } else {
        bw.write(order[i] + "\n");
    }
}
bw.flush();

 

- 출력

1
2
4
3
0