[백준] DFS와 BFS (1260번)

문제 이해

• 이 코드는 그래프 탐색 문제로, DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 인접 행렬로 구현합니다.
• 그래프의 각 노드는 1부터 시작하며, 주어진 노드로부터 연결된 모든 노드를 순서대로 탐색합니다.
• 입력으로 주어지는 간선 정보를 통해 무방향 그래프를 구성하고, 두 가지 탐색 방법으로 탐색 결과를 출력합니다.

핵심 아이디어

1. 그래프를 인접 행렬로 표현:
   • 노드 간의 연결을 2차원 배열에 저장합니다.
   • 만약 두 노드가 연결되어 있다면 해당 위치에 1을 표시합니다.
2. DFS(깊이 우선 탐색):
   • 한 노드에서 출발해 인접 노드를 재귀적으로 방문합니다.
   • 재귀 호출을 사용해 그래프의 모든 연결된 노드를 탐색합니다.
3. BFS(너비 우선 탐색):
   • 큐(Queue)를 사용해 노드들을 순서대로 탐색합니다.
   • 한 노드에서 출발해 같은 레벨의 인접 노드들을 모두 방문한 후 다음 레벨로 이동합니다.

알고리즘 흐름

1. 그래프 초기화: 노드와 간선 수를 입력받고, 인접 행렬을 구성합니다.
2. DFS 수행: 재귀를 통해 주어진 노드에서부터 연결된 모든 노드를 방문합니다.
3. BFS 수행: 큐를 사용해 같은 레벨의 인접 노드를 순차적으로 탐색합니다.
4. 탐색 결과 출력: DFS와 BFS 탐색 결과를 각각 출력합니다.

 

---

정답은 더보기 클릭

import java.util.*; // Scanner, Queue 등 자바 유틸리티 라이브러리 사용

class Main {
    
    static int[][] graph; // 그래프를 저장할 인접 행렬
    static StringBuilder dfsResult = new StringBuilder(); // DFS 탐색 결과를 저장할 변수
    static StringBuilder bfsResult = new StringBuilder(); // BFS 탐색 결과를 저장할 변수

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); // 입력을 받기 위한 Scanner 객체 생성

        // 노드 수, 간선 수, 탐색을 시작할 노드 입력
        int node = in.nextInt(); 
        int link = in.nextInt();
        int curNode = in.nextInt();

        in.nextLine(); // 개행 문자 처리

        // 그래프 초기화: 노드 번호를 1부터 사용하기 위해 [node+1][node+1] 크기로 생성
        graph = new int[node + 1][node + 1]; 

        // 간선 정보 입력 및 인접 행렬에 저장
        for (int i = 0; i < link; i++) {
            String[] arr = in.nextLine().split(" ");
            int p1 = Integer.parseInt(arr[0]); // 첫 번째 노드
            int p2 = Integer.parseInt(arr[1]); // 두 번째 노드

            // 무방향 그래프이므로 양방향 연결 표시
            graph[p1][p2] = 1;
            graph[p2][p1] = 1;
        }

        // DFS 수행
        boolean[] visit = new boolean[graph.length]; // 방문 여부를 저장할 배열
        dfs(visit, curNode); // DFS 호출

        // BFS 수행
        bfs(curNode); // BFS 호출

        // 탐색 결과 출력
        System.out.println(dfsResult.toString().trim()); // DFS 결과 출력
        System.out.println(bfsResult.toString().trim()); // BFS 결과 출력
    }

    // BFS(너비 우선 탐색) 구현
    public static void bfs(int curNode) {
        boolean[] visit = new boolean[graph.length]; // 방문 여부를 저장할 배열
        visit[curNode] = true; // 시작 노드 방문 처리

        Queue<Integer> q = new LinkedList<>(); // BFS를 위한 큐 생성
        q.add(curNode); // 시작 노드를 큐에 추가

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            int node = q.poll(); // 큐에서 노드 하나를 꺼냄
            bfsResult.append(node + " "); // 방문한 노드를 결과에 추가

            // 해당 노드와 연결된 다른 노드 탐색
            for (int i = 1; i < graph.length; i++) {
                if (!visit[i] && graph[node][i] == 1) { // 방문하지 않은 인접 노드라면
                    q.add(i); // 큐에 추가
                    visit[i] = true; // 방문 처리
                }
            }
        }
    }

    // DFS(깊이 우선 탐색) 구현
    public static void dfs(boolean[] visit, int curNode) {
        dfsResult.append(curNode + " "); // 현재 노드를 결과에 추가
        visit[curNode] = true; // 방문 처리

        // 해당 노드와 연결된 다른 노드 탐색
        for (int i = 1; i < graph.length; i++) {
            if (!visit[i] && graph[curNode][i] == 1) { // 방문하지 않은 인접 노드라면
                dfs(visit, i); // 재귀적으로 DFS 수행
            }
        }
    }
}