[1260] DFS와 BFS

🔗 문제 링크

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

🔍 문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

⚠️ 제한사항

• $(1 ≤ N ≤ 1,000), (1 ≤ M ≤ 10,000)$

• 입력으로 주어지는 간선은 양방향이다.

• 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.

🗝 풀이 (언어 : Java)

입력값을 받아서 사용하는 것이 까다로웠다. 그래프를 자바에서 나타내는 형태는 인접 행렬과 인접 리스트가 있다. 인접 행렬과 인접 리스트는 시간복잡도와 공간 복잡도가 서로 달라서, 그때그때 괜찮아 보이는 것으로 골라서 사용한다. 보통 인접 행렬은 인접하지 않은 곳도 전부 탐색해야 하기때문에, 인접 리스트를 사용했다. 하지만 이 방법은 인접한 원소의 값의 크기 순서를 보장하지 않으므로, 문제의 조건을 충족하려면 입력값을 다시 정렬해서 넣어주어야 했다. 다음 원소를 조회할 때, 방문한적 없는 원소만 추가하도록 했다. 나머지는 알고있는 BFS, DFS대로 코드를 작성했다. 양방향 그래프라 입력시에 받은 숫자 두개를 반대 순서로도 리스트에 넣어주어야 하는 것을 주의하자.

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

class Main {
    private static StringBuilder dfsString = new StringBuilder();
    private static StringBuilder bfsString = new StringBuilder();

    private static void dfs(int v, ArrayList<Integer>[] adj, boolean[] visitedD) {
        visitedD[v] = true;
        dfsString.append(v).append(' ');
        // 해당 원소와 연결된 모든 원소들 다음 순서로 조회
        for (Integer num : adj[v]) {
            // 방문한적 없는 원소만 다음으로 조회
            if (!visitedD[num])
                dfs(num, adj, visitedD);
        }
    }

    private static void bfs(int v, ArrayList<Integer>[] adj, boolean[] visitedB) {
        Queue<Integer> queue = new LinkedList<>();
        // 첫원소 넣어주고 방문 체크
        queue.add(v);
        visitedB[v] = true;
        // 큐의 원소가 모두 사라질 때까지 반복
        while (!queue.isEmpty()) {
            int next = queue.poll();
            bfsString.append(next).append(' ');
            for (Integer num : adj[next]) {
                // 방문한적 없는 원소만 다음으로 조회
                if (!visitedB[num]) {
                    queue.add(num);
                    visitedB[num] = true;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
        ArrayList<Integer>[] adj = new ArrayList[n + 1];
        // 배열의 각 인덱스별 ArrayList로 채워주기
        for (int i = 1; i <= n; i++)
            adj[i] = new ArrayList<>();
        // 이미 방문한적 있는지 확인 배열
        boolean[] visitedD = new boolean[n + 1], visitedB = new boolean[n + 1];
        for (int i = 0; i < m; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            int n1 = Integer.parseInt(st2.nextToken()), n2 = Integer.parseInt(st2.nextToken());
            adj[n1].add(n2); // 양방향 그래프 이므로 반대로도 입력해주어야 한다
            adj[n2].add(n1);
        }
        // 작은 숫자 순으로 방문하라고 했으므로 정렬해주기
        for (int i = 1; i <= n; i++)
            Collections.sort(adj[i]);
        br.close();
        dfs(v, adj, visitedD);
        bfs(v, adj, visitedB);
        System.out.println(dfsString);
        System.out.print(bfsString);
    }
}