[백준 1260번] DFS와 BFS

문제 링크: 1260번 제목

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

 

DFS와 BFS를 구현해보는 가장 기초적인 문제이다.

 

먼저 그래프 문제의 경우 입력부터 신경쓸 필요가 있다. 그래프가 인접 행렬로 주어진 경우와 인접 리스트로 주어진 경우를 나누어 생각해야 한다.

 

인접 행렬로 주어지는 경우에는 2차원 배열로 받는 것이 일반적이며, 인접 리스트로 주어지는 경우에는 ArrayList[]를 쓰는 편이 좋다. 2중 ArrayList를 사용하게 되면 get과 set을 사용하게 되어 보기에 흉하다(?). 다만 원칙은 2중 ArrayList를 쓰는 것이며, 따라서 컴파일 경고를 피할 수는 없으며 무시할 수는 있다.

 

DFS는 stack을 별도로 만들어두고서 함수를 호출해도 되지만, 재귀적으로 구현하는 편이 조금 더 쉽다. DFS의 경우 함수에 진입한 이후 방문 여부 확인 및 방문 처리를 한다는 점을 유념한다.

한편 BFS는 큐를 만들어두고 가장 첫 방문 노드를 미리 큐에 넣고서, 큐가 빌 때까지 계속해서 다음 노드를 찾아 나간다. 이 때 어떤 노드에서 다음 노드를 확인할 때에 큐에 넣기 전 미리 방문 여부 확인과 방문 처리를 한다는 점을 유념한다.

 

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

public class Main {
    static ArrayList<Integer>[] graph;
    static boolean[] visit;
    static StringBuilder sb = new StringBuilder();

    static void dfs(int n) {
        if (visit[n]) return;
        visit[n] = true;
        sb.append(n).append(' '); // 출력

        for (int item : graph[n])
            dfs(item);
    }

    static void bfs(int n, Queue<Integer> queue) {
        while (!queue.isEmpty()) {
            int cur = queue.poll();

            for (int item : graph[cur]) {
                if (visit[item]) continue;
                queue.offer(item);
                visit[item] = true;
                sb.append(item).append(' ');
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = temp[0];
        int m = temp[1];
        int v = temp[2];

        graph = new ArrayList[n+1];
        for (int i = 0; i < n+1; i++)
            graph[i] = new ArrayList<Integer>();

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int p1 = Integer.parseInt(st.nextToken());
            int p2 = Integer.parseInt(st.nextToken());

            graph[p1].add(p2);
            graph[p2].add(p1);
        }

        for (int i = 0; i < n; i++)
            Collections.sort(graph[i]);

        // DFS
        visit = new boolean[n+1];
        dfs(v);

        sb.append('\n');

        // BFS
        visit = new boolean[n+1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        visit[v] = true;
        sb.append(v).append(' ');
        bfs(v, queue);

        System.out.println(sb);
    }
}