백준 - 알고리즘 수업 (24444) - Java

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

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

---

[문제 해결]

• ArrayList로 무방향 그래프를 만들어준다.
• ArrayList를 오름차순 정렬한다.
• bfs를 순회하면서 방문하지 않은 노드를 방문 처리하고 방문한 순서를 기록해준다.

---

[Java]

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


public class Main{
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    static boolean visited[];
    static int result[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        result = new int[m+1];

        for(int i=0; i<=m; i++) list.add(new ArrayList<>());

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
        }

        for(int i=1; i<=m; i++){
            var pos = list.get(i);
                Collections.sort(pos);
            }


        bfs(start, m);

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

    public static void bfs(int start, int m){
        int cnt = 1;
        visited = new boolean[m+1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        result[start] = cnt++;

        while(!queue.isEmpty()){
            int cur = queue.poll();

            for(int num : list.get(cur)){
                if(!visited[num]){
                    queue.add(num);
                    visited[num] = true;
                    result[num] = cnt++;
                }
            }
        }
    }
}

---

처음에 2차원 배열로 그래프를 만들어 주었는데, 메모리 초과 떠서 ArrayList로 수정했습니다.

 

그리고 문제를 푸실때 주의 하실 점은,

 

1~m까지 순서대로 정점들의 방문한 순서를 출력해주어야 합니다.