[백준 - 1260] DFS와 BFS .java

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

 

 

Solution

방문할 수 있는 정점이 여러 개이면 정점 번호가 작은 것을 먼저 방문해야 한다
-> 오름차순으로 먼저 정렬한 뒤에 DFS, BFS 수행

 

 

 

DFS보다 BFS를 덜 구현해서 그런지 약간 어색했지만 재귀함수로 하지 않아 더 편했다.

 

import java.util.*;

public class Main {
    static boolean[] visited; // 방문 여부를 저장하는 배열
    static ArrayList<Integer>[] nums; // 인접 리스트를 저장하는 배열

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 노드 개수
        int m = sc.nextInt(); // 에지 개수
        int start = sc.nextInt(); // 시작점

        // 시작 노드가 1부터 시작하도록 배열 크기를 n+1로 설정
        nums = new ArrayList[n + 1];

        // 인접 리스트 초기화
        for (int i = 1; i <= n; i++) {
            nums[i] = new ArrayList<Integer>();
        }
        
        // 에지 정보 저장
        for (int i = 0; i < m; i++) {
            int s = sc.nextInt(); // 시작 노드
            int e = sc.nextInt(); // 끝 노드
            nums[s].add(e); // 시작 노드에서 끝 노드로의 에지 추가
            nums[e].add(s); // 끝 노드에서 시작 노드로의 에지 추가 (무방향 그래프)
        }

        // 오름차순으로 노드 접근을 위해 각 노드의 인접 리스트 정렬
        for (int i = 1; i <= n; i++) {
            Collections.sort(nums[i]);
        }

        // DFS 실행
        visited = new boolean[n + 1]; // 방문 배열 초기화
        Main.DFS(start); // 시작점부터 DFS 탐색
        System.out.println(); // 출력 형식을 위한 줄바꿈

        // BFS 실행
        visited = new boolean[n + 1]; // 방문 배열 초기화
        BFS(start); // 시작점부터 BFS 탐색
        System.out.println(); // 출력 형식을 위한 줄바꿈
    }

    // DFS (깊이 우선 탐색) 메서드
    public static void DFS(int now) {
        // 현재 노드를 방문했으므로 출력
        System.out.print(now + " ");
        visited[now] = true; // 현재 노드 방문 처리

        // 현재 노드와 연결된 모든 노드를 방문
        for (int i : nums[now]) {
            if (!visited[i]) { // 방문하지 않았다면
                DFS(i); // 재귀적으로 DFS 호출
            }
        }
    }

    // BFS (너비 우선 탐색) 메서드
    public static void BFS(int now) {
        Queue<Integer> q = new LinkedList<Integer>(); // BFS를 위한 큐 생성
        // 현재 노드를 큐에 삽입
        q.add(now);
        // 현재 노드 방문 처리
        visited[now] = true;

        while (!q.isEmpty()) {
            // 큐에서 노드를 꺼내서
            int node = q.poll();
            // 출력
            System.out.print(node + " ");
            // 꺼낸 노드와 연결된 모든 노드를 방문
            for (int i : nums[node]) {
                if (!visited[i]) { // 방문하지 않았다면
                    // 방문 처리
                    visited[i] = true;
                    // 큐에 삽입
                    q.add(i);
                }
            }
        }
    }
}