Java 백준 문제풀이 (29) 2444: 알고리즘 수업 - 너비 우선 탐색 1

나 성공했는데 왜 계속 실패 딱지 붙지..?

 

오늘은 너비 우선 탐색이다.

바로 이전 글에 있는 dfs(깊이 우선 탐색)문제를 풀었다면 쉽게 풀 수 있다.

물론 최소한의 이론은 알고 와야 한다.

 

 

 

헷갈릴 때는 이 그림을 떠올려보자.

왜 BFS에서는 Queue를 이용한 반복문을 돌리고 DFS에서는 재귀호출로 처리하는지 이해가 될 것이다.

이 그림을 보고 왜 Queue를 써야하는지 이해가 되지 않는다면 BFS가 아니라 Queue를 다시 공부해야 한다.

어차피 문제에서 기본적인 풀이 방법은 모두 제시하고 있으므로 코드별로 나누어 해당 코드를 작성한 이유를 설명하는 것으로 진행한다.

 

 

 

 

 

 

 

 

 

전체 코드

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

public class Main {
    static boolean[] visited;
    static int[] order;
    static int count = 0;
    static ArrayList<ArrayList<Integer>> edges = new ArrayList<>();
    static LinkedList<Integer> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int vertex = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        for (int i=0; i<=vertex; i++) {
            edges.add(new ArrayList<>());
        }

        for (int i=0; i<edge; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            edges.get(num1).add(num2);
            edges.get(num2).add(num1);
        }

        for (ArrayList<Integer> list : edges) {
            Collections.sort(list);
        }

        visited = new boolean[vertex+1];
        order = new int[vertex+1];

        bfs(start);

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

    static void bfs (int v) {
        visited[v] = true;
        order[v] = ++count;
        queue.add(v);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for ( int i=0; i< edges.get(current).size(); i++) {
                int x = edges.get(current).get(i);
                if (!visited[x]) {
                    visited[x] = true;
                    order[x] = ++count;
                    queue.add(x);
                }
            }
        }
    }
}

 

 

 

 

 

static boolean[] visited;
static int[] order;
static int count = 0;
static ArrayList<ArrayList<Integer>> edges = new ArrayList<>();
static LinkedList<Integer> queue = new LinkedList<>();

1. 재귀가 아니기 때문에 DFS와 달리 visited, order, count, LinkedList가 모두 bfs() 메서드 안으로 들어가도 상관 없다.

실제 프로그램이라고 생각했을 때는 이렇게 죄다 static으로 빼놓으면 안 될 것이다.

 

2. ArrayList를 사용한 이유는 빠르고 배열 크기 관리하기 편해서이다. 다른 어떤 자료구조를 사용해도 상관 없다.

 

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");

int vertex = Integer.parseInt(st.nextToken());
int edge = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());

돌려본 결과 2.6초가 나오는데 StringTokenizer는 몰라도 BufferedReader 안 쓰면 시간 초과 나올 듯.

 

 

 

for (int i=0; i<=vertex; i++) {
    edges.add(new ArrayList<>());
}

for (int i=0; i<edge; i++) {
    st = new StringTokenizer(br.readLine(), " ");
    int num1 = Integer.parseInt(st.nextToken());
    int num2 = Integer.parseInt(st.nextToken());

    edges.get(num1).add(num2);
    edges.get(num2).add(num1);
}

정점 개수+1개 만큼 ArrayList를 생성한다. (정점의 시작이 1번이기 때문에)

무방향 그래프이기 때문에 간선 정보를 각 정점에 그대로 다 넣어주면 된다.

 

 

 

for (ArrayList<Integer> list : edges) {
    Collections.sort(list);
}

visited = new boolean[vertex+1];
order = new int[vertex+1];

bfs(start);

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

오름차순으로 정렬, visited랑 order에 입력받은 값에 따라 배열 크기 부여하고 메서드 실행, 결과물로 정점 방문 순서 출력.

visited와 order의 크기가 +1인 것은 정점의 시작이 1번이기 때문에 0번 인덱스는 사용하지 않을 것이기 때문이다.

 

 

 

 

 

static void bfs (int v) {
    visited[v] = true;
    order[v] = ++count;
    queue.add(v);

    while (!queue.isEmpty()) {
        int current = queue.poll();
        for ( int i=0; i< edges.get(current).size(); i++) {
            int x = edges.get(current).get(i);
            if (!visited[x]) {
                visited[x] = true;
                order[x] = ++count;
                queue.add(x);
            }
        }
    }

메서드 내용은 문제에서 제시해주고 있기 때문에 거의 그대로 갖다 붙이면 된다.

혹시 queue를 왜 쓰는지 이해가 잘 안된다면 문제를 푸는 의미가 없다. 위의 그래프 이미지를 보면서 다시 한 번 생각해보자.