[ 백준 - Java ] DFS와 BFS ( 자바 )

( dfs / DFS와 BFS / 1260 )

[문제]

문제 설명

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

입출력 예시

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

 

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

---

[코드]

import java.util.*;

class DfsAndBfs1260 {
    static List<Integer>[] arr;     // 인접 리스트 표현
    static List<Integer> dfsResult; // dfs 결과
    static List<Integer> bfsResult; // bfs 결과
    static boolean[] check;         // 방문여부 체크

    public static void main(String[] args) {
        // === 입력 ===
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int len = sc.nextInt();
        int start = sc.nextInt();

        arr = new List[n + 1];

        for(int i = 0; i <= n; i++) arr[i] = new ArrayList<>();

        for(int i = 0; i < len; i++) {
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            // 양방향 모두 표시
            arr[n1].add(n2);
            arr[n2].add(n1);
        }

        sc.close();

        // === 구현 ===
        // 인접 리스트 정렬 ( 작은수부터 방문하기 위해 )
        for(List<Integer> node : arr) Collections.sort(node);

        dfsResult = new ArrayList<>();
        bfsResult = new ArrayList<>();

        check = new boolean[n + 1];
        dfs(start);     // dfs 시작점 부터

        Arrays.fill(check, false);  // check 전부 false로 초기화
        bfs(start);     //bfs 시작점 부터
        
        // === 결과 출력 ===
        for(int i = 0; i < dfsResult.size(); i++){
            System.out.print(dfsResult.get(i) + " ");
        }
        System.out.println();
        for(int i = 0; i < bfsResult.size(); i++){
            System.out.print(bfsResult.get(i) + " ");
        }
    }
    // 깊이우선
    public static void dfs(int idx){
        if(check[idx]) return;

        check[idx] = true;          // 현재 위치 방문처리
        dfsResult.add(idx);         // 결과에 현재 위치 추가

        // 현재 노드에서 방문 가능한 노드중에 아직 방문 안한 노드 재귀호출
        for(int x : arr[idx]){      
            if(!check[x]) dfs(x);
        }
    }
    // 너비우선
    public static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();  // 방문할 노드를 저장하는 용도
        q.offer(start);         // 처음 값 추가
        check[start] = true;    // 처음 값 방문처리
        
        while(!q.isEmpty()){
            int x = q.poll();   // 먼저 삽입된 값 pop
            bfsResult.add(x);   // 결과 추가

            // 현재 노드에서 방문 가능한 노드중에 아직 방문 안한 노드 체크하며 큐에 추가
            for(int y : arr[x]){    
                if(!check[y]) {
                    check[y] = true;
                    q.add(y);
                }
            }
        }
    }
}

문제 링크

1260번: DFS와 BFS

제가 잘못 알고 있거나 잘못된 부분이 있을 경우 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄