[Java] 백준(실버-2) 24444번 - 알고리즘 수업(너비 우선 탐색 1)

문제 분석

---

작성코드

---

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

class Main {
    //
    public static int N, M;
    // 방문한 정점을 담을 배열
    public static int[] visited;
    // 인접 리스트
    public static List<List<Integer>> list;

    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());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        // 방문 배열 초기화
        visited = new int[N+1];

        // 인접리스트 초기화(1 ~ N)
        list = new ArrayList<>();
        for(int i=1; i<=N+1; i++) {
            list.add(new ArrayList<Integer>());
        }

        // M개의 간선 입력받으며 인접리스트 구현
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            // 무방향이기에 양쪽 정점을 모두 추가
            list.get(start).add(end);
            list.get(end).add(start);
        }

        // 인접리스트의 각 노드 오름차순 정렬
        for(int i=1; i<list.size(); i++) {
            Collections.sort(list.get(i));
        }

        BFS(R);

        for(int i=1; i<visited.length; i++) {
            bw.write(visited[i]+"\n");
        }
        
        bw.flush();
        bw.close();
        br.close();
    }

    private static void BFS(int start) {
        // 큐를 선언하고 시작점 삽입
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        // 방문 순서
        int cnt = 1;

        // 방문 배열에 1번째 시작점 저장
        visited[start] = cnt;
        cnt++;

        // 큐가 빌 때 까지 BFS를 반복한다.
        while(!q.isEmpty()) {
            // 현재 노드 꺼내기
            int now = q.poll();
            // 꺼낸 노드의 인접노드를 큐에 삽입하고 방문 여부 기록하기
            // 이 때, 이미 방문한 노드는 큐에 삽입하지 않음.
            for(int next : list.get(now)) {
                if(visited[next] != 0) {
                    continue;
                }
                q.offer(next);
                visited[next] = cnt++;
            }

        }
    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.