문제 출처

단계별로 풀어보기 > 그래프와 순회 > 너비 우선 탐색 2
https://www.acmicpc.net/problem/24445

문제 설명

N개의 정점, M개의 간선, 시작 노드 정보 R이 주어질 때, BFS로 순회하는 노드 순서를 출력하라

접근 방법

인접 리스트 배열 graph를 생성하여 간선 정보를 삽입한다. 이를 BFS로 해결한다.

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

public class 너비_우선_탐색_2 {
    static int[] visited;
    static List<Integer>[] graph;
    static int index = 0;

    public static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = ++index;

        while(!q.isEmpty()){
            int point = q.poll();
            for(int i = 0; i<graph[point].size(); i++){
                int next = graph[point].get(i);
                if(visited[next] == 0){
                    visited[next] = ++index;
                    q.offer(next);
                }
            }
        }

    }
    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());

        graph = new ArrayList[N+1];
        visited = new int[N+1];

        for(int i = 0; i<=N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int j = 0; j<M; j++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }

        for(int k = 1; k<=N; k++){
            Collections.sort(graph[k], Collections.reverseOrder());
        }

        bfs(R);
        for(int l = 1; l<=N; l++){
            bw.write(visited[l] + "\n");
            bw.flush();
        }
        bw.close();
        br.close();
    }
}

Review

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

public class 너비_우선_탐색_2_review {
    static int visited[];
    static List<Integer>[] graph;
    static int index = 1;

    public static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = index++;
        while(!q.isEmpty()){
            int point = q.poll();
            for(int k : graph[point]){
                if(visited[k]>0) continue;
                q.offer(k);
                visited[k] = index++;
            }
        }

    }
    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());

        graph = new ArrayList[N+1];
        visited = new int[N+1];

        for(int i = 0; i<=N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int j = 1; j<=M; j++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);
            graph[b].add(a);
        }

        for(List k : graph){
            Collections.sort(k, Collections.reverseOrder());
        }

        bfs(R);

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

알게된 점

BFS를 진행할 때, 큐에서 poll할 때, visited에 노드 정보를 입력하게 된다면 중복이 발 생할 수 있다. 따라서 point 노드와 연결 된 노드들을 큐에 삽입할 때, visited에 표시를 한다.

문제푼 흔적

Review