BOJ 1260 DFS와 BFS [Java]

BOJ 1260 DFS와 BFS

1. 문제 링크

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

2. 문제 해설

그래프에서의 dfs와 bfs를 할 수 있는지를 묻는 문제이다. 인접 리스트를 이용하여 그래프를 표현해주고 dfs와 bfs를 돌려주면 된다.

주의할 점
1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점이다.
: 인접 리스트에서 각 정점의 원소들을 오름차순으로 정렬해주면 쉽게 해결할 수 있다.

2. dfs를 비재귀적인 방식으로 풀 경우 재귀적인 dfs와 방문 순서가 다를 수 있다.
: 나는 dfs를 재귀적인 방식으로 풀었지만, 재귀적인 방식이 아닌 stack을 이용해서 풀 경우 방문 처리를 제대로 해주지않으면 재귀적인 방식과 방문 순서가 달라지게 될 수 있다. 내가 bfs에서 큐에 넣을 때 vis[nxt]를 true로 처리한 것과 같은 방식으로 스택에 넣을 때 방문을 했다고 처리하면 안된다.
재귀적인 방식은 실제 방문을 할 때 방문 표시를 남기는 반면에 비재귀적인 방식은 방문하기 전에 아직 방문하지 않은 곳을 발견하면 그 때 방문 표시를 남겨버리기 때문에 이러한 차이가 발생한다. 그렇다면 stack을 이용해서 어떻게 재귀적인 방식처럼 동작하도록 할 수 있을까?

static void dfs() {
        sta.add(v);
        vis = new boolean[n];

        while (!sta.isEmpty()) {
            int cur = sta.pop();

            if (vis[cur]) {
                continue;
            }

            vis[cur] = true;
            sb.append(cur + 1).append(' ');

            for (int i = 0; i < adj.get(cur).size(); i++) {
                int nxt = adj.get(cur).get(adj.get(cur).size() - 1 - i);

                if (vis[nxt]) {
                    continue;
                }

                sta.add(nxt);
            }
        }

        sb.append('\n');
    }

위와 같이 스택에서 뺄 때 방문을 했다고 처리하면 재귀적인 dfs와 방문 순서가 동일하다. 다만 이렇게 하면 스택에 같은 정점의 값이 여러 번 들어갈 수 있지만, 8~10줄 코드를 통해 각 정점마다 연결된 정점을 보는 작업은 1번씩만 하도록 처리해놓아서 시간복잡도는 동일하게 유지할 수 있다.
16번째 줄은 스택에서 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 법칙을 지켜주기위해 저렇게 처리하였다.

3. 코드 보기

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

public class Main {
    static StringBuilder sb;
    static int n;
    static int m;
    static int v;
    static boolean[] vis;
    static ArrayList<ArrayList<Integer>> adj;
    static Queue<Integer> q;

    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());
        sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken()) - 1;
        vis = new boolean[n];
        adj = new ArrayList<>();
        q = new LinkedList<>();

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

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;

            adj.get(from).add(to);
            adj.get(to).add(from);
        }

        for (int i = 0; i < n; i++) {
            Collections.sort(adj.get(i));
        }

        dfs(v);
        bfs();

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }

    static void dfs(int idx) {
        if (idx == n) {
            return;
        }

        vis[idx] = true;
        sb.append(idx + 1).append(' ');

        for (int i = 0; i < adj.get(idx).size(); i++) {
            int nxt = adj.get(idx).get(i);

            if (vis[nxt]) {
                continue;
            }

            dfs(nxt);
        }
    }

    static void bfs() {
        sb.append('\n');
        q.add(v);
        vis = new boolean[n];
        vis[v] = true;

        while (!q.isEmpty()) {
            int cur = q.poll();
            sb.append(cur + 1).append(' ');

            for (int i = 0; i < adj.get(cur).size(); i++) {
                int nxt = adj.get(cur).get(i);

                if (vis[nxt]) {
                    continue;
                }

                q.add(nxt);
                vis[nxt] = true;
            }
        }
    }
}