[백준] DFS와 BFS

출처

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

1260번: DFS와 BFS

문제

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

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

입출력 예제

내 코드

DFS와 BFS의 정형적인 방식으로 풀면된다.

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

public class Main {
    static int N;// 정점 개수
    static int M;// 간선 개수
    static int start;// 시작 정점
    static int[][] mat;// 간선 연결상태
    static boolean[] visit;// 방문 여부

    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        start = sc.nextInt();
        mat = new int[1001][1001];
        visit = new boolean[1001];

        // 간선 연결상태 저장
        for (int i = 0; i < M; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            mat[x][y] = mat[y][x] = 1;
        }

        dfs(start);
        visit = new boolean[1001];
        System.out.println();
        bfs();
    }

    // 깊이 우선 1부터 시작
    public static void dfs(int i) {
        // 정점 1 방문 true
        visit[i] = true;
        // 출력
        System.out.print(i + " ");

        // 아직 방문하지 않았고 방문해야하는 곳이면
        // 정점 1부터 시작하므로
        // 1~ 정점 개수까지
        for (int j = 1; j <= N; j++) {
            // 아직 방문하지 않은 정점이고
            // 연결된 정점이라면
            if (visit[j] == false && mat[i][j] == 1) {
                // 재귀로 해당 정점 들어가기
                dfs(j);
            }
        }
    }

    // 너비 우선
    public static void bfs() {
        Queue<Integer> queue = new LinkedList();
        queue.offer(start);// 시작 정점 넣기
        visit[start] = true;// 시작정점 방문
        System.out.print(start + " ");// 시작 정점 출력

        while (!queue.isEmpty()) {// 큐 빌때까지 도는데
            int temp = queue.poll();// 큐에 있는 값 일단 빼서 저장

            // 1부터 정점 개수만큼 돌기
            for (int j = 1; j <= N; j++) {
                // 아직 방문하지 않았고
                // 같은 너비의 정점이라면
                if (visit[j] == false && mat[temp][j] == 1) {
                    // 큐에 넣고
                    queue.offer(j);
                    // 방문하고
                    visit[j] = true;
                    // 해당 정점 출력
                    System.out.print(j + " ");
                }
            }
        }
    }
}