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

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

문제

---

문제 설명

노드들에 대한 정보가 주어졌을 때 BFS를 사용했을 때 정점의 방문 순서를 오름차순으로 출력하는 문제이다.

노드들의 정보를 저장하기 위해 ArrayList 를 담을 배열을 선언하고 해당 정보에 양방향 간선에 대한 정보를 저장해주었다.

for (int i = 1; i <= n; i++) {
	nodes[i] = new ArrayList<>();
}

for (int i = 0; i < m; i++) {
	st = new StringTokenizer(br.readLine());
	int u = Integer.parseInt(st.nextToken());
	int v = Integer.parseInt(st.nextToken());

	nodes[u].add(v);
	nodes[v].add(u);
}

그리고 이번 문제에서 인접 정점을 오름차순으로 방문한다고 하였기 때문에 각 노드들의 인접 노드들을 오름차순으로 정렬을 해주어야한다. 처음 풀었을 때 이 조건을 생각을 안하고 풀어서 답이 이상하게 나왔었다.

for (int i = 1; i <= n; i++) {
	Collections.sort(nodes[i]);
}

이렇게 한 후에는 BFS 의 순서대로 시작 정점인 r을 Queue에 넣어주고 해당 정점을 방문처리 하고 index 를 선언해서 몇번째로 방문했는지 저장해줄 수 있게 하였다.

queue.add(r);
visited[r] = true;
int index = 1;

while (!queue.isEmpty()) {
	int cur = queue.poll();
	result[cur] = index;
	index++;

	for (Integer i : nodes[cur]) {
		if (!visited[i]) {
			queue.add(i);
			visited[i] = true;
		}
	}
}

그렇게 하고 출력만 해주면 이번 문제는 끝이 나게 된다.

완성된 코드는 아래와 같다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_24444 {
    static int n, m, r;
    static List<Integer>[] nodes;
    static Queue<Integer> queue;
    static int[] result;
    static boolean[] 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());

        queue = new LinkedList<>();
        nodes = new List[n + 1];
        result = new int[n + 1];
        visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            nodes[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            nodes[u].add(v);
            nodes[v].add(u);
        }

        for (int i = 1; i <= n; i++) {
            Collections.sort(nodes[i]);
        }

        queue.add(r);
        visited[r] = true;
        int index = 1;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            result[cur] = index;
            index++;

            for (Integer i : nodes[cur]) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            System.out.println(result[i]);
        }
    }
}