[백준/Java] 1260번 DFS와 BFS

문제

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

입력

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

출력

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

---

나의 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    
    static int[][] graph; // 그래프를 인접 행렬로 표현
    static boolean visited[]; // 방문 여부를 기록하는 배열
    static int N; // 노드의 수
    static int M; // 간선의 수
    static int start; // 탐색 시작 노드
    
    // 깊이 우선 탐색(DFS)
    public static void dfs(int i) {
        visited[i] = true; // 현재 노드 방문 표시
        System.out.print(i + " "); // 방문한 노드 출력
        
        // 인접한 노드들을 탐색
        for (int j = 1; j <= N; j++) {
            if (graph[i][j] == 1 && !visited[j]) { // 인접하고 방문하지 않은 노드
                dfs(j); // 재귀 호출로 깊이 우선 탐색
            }
        }
    }
    
    // 너비 우선 탐색(BFS)
    public static void bfs(int i) {
        Queue<Integer> q = new LinkedList<>(); // 큐 생성
        q.offer(i); // 시작 노드를 큐에 추가
        visited[i] = true; // 시작 노드 방문 표시
        System.out.print(i + " "); // 방문한 노드 출력
        
        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            int tmp = q.poll(); // 큐에서 노드를 꺼냄
            
            // 인접한 노드들을 탐색
            for (int j = 1; j <= N; j++) {
                if (graph[tmp][j] == 1 && !visited[j]) { // 인접하고 방문하지 않은 노드
                    q.offer(j); // 큐에 노드 추가
                    visited[j] = true; // 노드 방문 표시
                    System.out.print(j + " "); // 방문한 노드 출력
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); 
        N = sc.nextInt(); 
        M = sc.nextInt(); 
        start = sc.nextInt(); 
        
        graph = new int[1001][1001]; 
        visited = new boolean[1001]; 
        
        // 간선 정보 입력
        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = graph[b][a] = 1; // 무방향 그래프
        }
        
        dfs(start);
        System.out.println();
        
        // 방문 배열 초기화
        for (int i = 1; i <= N; i++) {
            visited[i] = false;
        }
        
        bfs(start);
    }
}