백준 알고리즘 수업 - 너비 우선 탐색 4 (24447) - Java

---

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

24447번: 알고리즘 수업 - 너비 우선 탐색 4

---

[문제 해결]

• 방문한 순서를 기록할 배열 seq[]와, 깊이를 기록할 visited[] 배열을 만들어준다.
• 그래프가 만들어지면 인접 정점들을 오름차순 정렬을 해준다.
• bfs를 돌려준다.
• 주의 할점은 visited, seq 배열과 값을 곱하고 더해줄 ans변수를 long으로 해주어야 한다.    

---

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 long visited[];
    static long seq[];
    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());

        seq = new long[m+1];
        visited = new long[m+1];
        for(int i=1; i<=m; i++) visited[i] = -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);

        long ans = 0;
        for(int i=1; i<=m; i++)
            ans += seq[i] * visited[i];

        System.out.println(ans);

    }

    public static void bfs(int start, int m){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = 0;

        int seqCnt = 1;
        seq[start] = seqCnt++;

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

            for(int num : list.get(cur)){
                if(visited[num] == -1){
                    queue.add(num);
                    visited[num] = visited[cur] + 1;
                    seq[num] = seqCnt++;
                }
            }
        }
    }
}