[백준/자바] 1260번 - DFS와 BFS 구현하기

 

 

 

 

 

 

문제 풀이

 

 

 

문제 이해하기

 

 

설명:

• 주어진 그래프에서 DFS와 BFS 탐색 결과를 구하라.
• 탐색 시 노드 번호가 작은 순서부터 방문한다.

입력 조건:

• 노드의 수, 간선의 수, 시작 노드를 입력해야 한다.
• 간선은 양방향이다.

출력 조건:

• DFS 결과와 BFS 결과를 출력한다.

 

 

 

 

DFS와 BFS 간단 설명

 

 

DFS는 깊이 우선 탐색이며 한 노드를 방문한 후 그 노드와 연결된 노드를 재귀적으로 탐색한다.

 

재귀 호출 또는 스택을 사용하여 구현 가능하다.

 

 

BFS는 너비 우선 탐색이며 한 노드를 방문한 후 연결된 모든 노드를 큐에 넣어 순차적으로 탐색한다.

 

큐를 사용하여 구현 가능하다.

 

 

 

 

 

코드 구조

 

입력 처리:  노드,간선 정보를 입력받아 인접 행렬을 생성한다.

 

DFS 구현: 재귀 호출을 사용하여 깊이 우선으로 탐색한다.

 

BFS 구현: 큐를 사용하여 너비 우선으로 탐색한다.

 

출력: DFS 결과와 BFS 결과를 출력한다.

 

 

 

 

 

세부 구현

 

 

1. 입력 처리 및 그래프 초기화

• 입력을 빠르게 처리하기 위해서 BufferedReader을 사용했다.
• 그래프는 인접 행렬로 표현했다.
  • 행렬의 크기는 [node+1][node+1] 이다. (0번 노드를 사용하지 않을 것)
  • 간선 정보는 양방향으로 저장한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
node = Integer.parseInt(st.nextToken());  // 노드 수
line = Integer.parseInt(st.nextToken());  // 간선 수
start = Integer.parseInt(st.nextToken()); // 시작 노드

arr = new int[node + 1][node + 1];  // 인접 행렬 초기화
check = new boolean[node + 1];     // 방문 배열 초기화

for (int i = 0; i < line; i++) {
    StringTokenizer st1 = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st1.nextToken());
    int b = Integer.parseInt(st1.nextToken());
    arr[a][b] = arr[b][a] = 1; // 양방향 간선 저장
}

 

 

2. DFS 구현

• 재귀 호출을 통해서 한 방향으로 끝까지 탐색한다.
• 방문한 노드는 check 배열에 기록한다.

public static void dfs(int start) {
    check[start] = true; // 방문 표시
    sb.append(start + " "); // 결과에 추가

    for (int i = 1; i <= node; i++) {
        if (arr[start][i] == 1 && !check[i]) { // 연결되어 있고 방문하지 않았다면
            dfs(i); // 재귀 호출
        }
    }
}

 

 

 

3. BFS 구현

• 큐를 사용하여 노드를 차례대로 방문한다.
• 방문한 노드는 check 배열에 기록한다.

public static void bfs(int start) {
    q.add(start); // 시작 노드 큐에 추가
    check[start] = true; // 방문 표시

    while (!q.isEmpty()) {
        start = q.poll(); // 큐에서 노드 꺼냄
        sb.append(start + " "); // 결과에 추가

        for (int i = 1; i <= node; i++) {
            if (arr[start][i] == 1 && !check[i]) { // 연결되어 있고 방문하지 않았다면
                q.add(i); // 큐에 추가
                check[i] = true; // 방문 표시
            }
        }
    }
}

 

 

 

 

결과 출력

 

 

DFS를 수행한 후 개행문자( \n )로 구분하여 BFS 수행 결과를 출력한다.

 

방문 배열은 BFS 실행하기 전에 초기화한다.

 

dfs(start);
sb.append("\n"); // DFS 결과 끝에 줄바꿈 추가
check = new boolean[node + 1]; // 방문 배열 초기화
bfs(start);
System.out.println(sb.toString()); // 결과 출력

 

 

 

이렇게 입력했을 시

 

 

정상적으로 출력을 확인하였다.

 

 

 

최종 코드

 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Boj_1260 {

    // 효율적인 출력 처리를 위해 StringBuilder를 사용
    static StringBuilder sb = new StringBuilder();

    // 각 노드의 방문 여부를 저장하는 배열
    static boolean[] check;

    // 그래프를 인접 행렬로 표현하는 2차원 배열
    static int[][] arr;

    // 노드의 수, 간선의 수, 시작 노드를 저장하는 변수들
    static int node, line, start;

    // BFS에서 사용할 큐 (큐에 노드를 추가하여 순차적으로 방문)
    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {

        // BufferedReader를 사용하여 입력을 빠르게 받음
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 번째 줄에서 노드의 수, 간선의 수, 시작 노드를 입력 받음
        StringTokenizer st = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st.nextToken());  // 노드의 수
        line = Integer.parseInt(st.nextToken());  // 간선의 수
        start = Integer.parseInt(st.nextToken()); // 시작 노드

        // 인접 행렬을 노드 수 + 1 크기로 초기화 (0번 노드는 사용하지 않음)
        arr = new int[node + 1][node + 1];

        // 방문 여부 배열을 노드 수 + 1 크기로 초기화 (0번 노드는 사용하지 않음)
        check = new boolean[node + 1];

        // 간선 정보를 입력받아서 인접 행렬에 저장
        for (int i = 0; i < line; i++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());

            // 두 개의 노드 a, b가 간선으로 연결되어 있다는 정보를 입력받음
            int a = Integer.parseInt(st1.nextToken());
            int b = Integer.parseInt(st1.nextToken());

            // 간선이 양방향이므로 a -> b, b -> a 둘 다 1로 표시
            arr[a][b] = arr[b][a] = 1;
        }

        // DFS 탐색을 시작
        dfs(start);
        sb.append("\n");  // DFS가 끝나면 줄바꿈을 추가

        // BFS를 시작하기 전에 방문 여부 배열을 초기화
        check = new boolean[node + 1];

        // BFS 탐색을 시작
        bfs(start);

        // 최종적으로 StringBuilder에 저장된 결과를 출력
        System.out.println(sb.toString());
    }

    // DFS 함수 정의
    public static void dfs(int start) {
        // 현재 노드를 방문했다고 표시
        check[start] = true;
        // 현재 노드를 출력 (StringBuilder에 추가)
        sb.append(start + " ");

        // 현재 노드와 연결된 모든 노드를 재귀적으로 방문
        for (int i = 1; i <= node; i++) {
            // 연결된 노드이면서 아직 방문하지 않은 노드라면 DFS를 재귀적으로 호출
            if (arr[start][i] == 1 && !check[i]) {
                dfs(i);
            }
        }
    }

    // BFS 함수 정의
    public static void bfs(int start) {
        // 시작 노드를 큐에 추가하고 방문 표시
        q.add(start);
        check[start] = true;

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            // 큐에서 노드를 꺼내서 방문
            start = q.poll();
            sb.append(start + " "); // 현재 노드를 출력 (StringBuilder에 추가)

            // 현재 노드와 연결된 모든 노드를 큐에 추가하여 차례대로 방문
            for (int i = 1; i <= node; i++) {
                // 연결된 노드이고 아직 방문하지 않은 노드라면 큐에 넣고 방문 표시
                if (arr[start][i] == 1 && !check[i]) {
                    q.add(i);
                    check[i] = true;
                }
            }
        }
    }
}

 

 

이해가 안간다면 주석을 보면서 하나씩 천천히 판단하는 것이 좋을 것이다!

 

StringBuilder, BufferedReader,StringTokenizer에 대한 이해와 DFS,BFS 구현에 큰 도움이 된 문제였다.

 

 

 

 

 

 

문제를 풀었던 방법

 

 

dfs와 bfs를 직접 인접행렬을 그려가며 단계별로 초기값과 로직을 따라가며 설명했다.

 

초기 조건

 

DFS

• check = [false, false, false, false, false] → 각 노드의 방문 여부를 저장.
• sb = "" → 탐색 순서를 저장.

BFS

• check = [false, false, false, false, false]
• q = 빈 큐 → 다음에 방문할 노드를 저장.
• sb = ""

이런 식으로 정리하여

 

      1   2   3   4
1    [ 0   1   1   1 ]
2   [ 1   0   0   1 ]
3   [ 1   0   0   1 ]
4   [ 1   1   1   0 ]

 

이렇게 행렬을 그리고 노드 연결 상태를 확인하면서 로직을 이해했다.

 

 

DFS(1)을 호출했을 경우엔

 

 

• DFS(1):
  • check[1] = true, sb = "1 ".
  • 연결된 노드: 2, 3, 4.
  • dfs(2) 호출.
• DFS(2):
  • check[2] = true, sb = "1 2 ".
  • 연결된 노드: 1, 4.
    • 1은 이미 방문됨.
  • dfs(4) 호출.
• DFS(4):
  • check[4] = true, sb = "1 2 4 ".
  • 연결된 노드: 1, 2, 3.
    • 1, 2는 이미 방문됨.
  • dfs(3) 호출.
• DFS(3):
  • check[3] = true, sb = "1 2 4 3 ".
  • 연결된 노드: 1, 4.
    • 모두 방문됨 → 재귀 종료.

이런 식으로 정리해가며 푸니 머리 속에 이해가 됐다. 사람 머리는 컴퓨터가 아니고 나도 똑똑한 사람이 아니라 이렇게 하나씩 정리해가며 푸니 금방 잊지 않고 설명할 수 있게 되었다.

 

한 3시간 걸린것 같다. DFS와 BFS 문제에 좀 익숙해져서 다른 문제들도 시간 단축을 할 것이다.