[BOJ_1260] DFS와 BFS (java)

문제

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

어려웠던 점

• BFS, DFS를 구현하는데 왜 인접행렬을 구현해야하는가 ?
• 인접행렬 vs 인접리스트 차이
• DFS, BFS 구현 방법 미숙지

1. 왜 인접행렬을 구현해야하는가?

• BFS와 DFS를 구현할 때 그래프를 표현하는 방식이 필요하기 때문이다.
• 그래프를 표현하는 방법에는 크게 두 가지가 있다. -> 인접 행렬, 인접 리스트

2. 인접 행렬 vs 인접 리스트

1) 인접 행렬

• 2차원 배열을 사용해서 노드 간의 연결 정보를 저장하는 방식
• map[N+1][N+1]이 바로 인접 행렬을 의미
• map[i][j] = 1이면 i번 정점과 j번 정점이 연결되었다는 의미

✅ 왜 인접 행렬을 사용했을까?

1. 구현이 단순

• map[i][j] 값만 보면 노드 간의 연결 여부를 바로 알 수 있음
• 정점이 연결되어 있는지 확인하는 연산이 O(1)로 빠르게 수행됨

2. 작은 그래프에 적합

• N ≤ 1000 정도의 크기를 가정하면 무난하게 동작
• 공간 복잡도는 O(N^2)이지만, N이 크지 않다면 사용하기 좋음

2) 인접 리스트

• 리스트를 사용해 각 정점의 연결된 노드들을 저장하는 방식
• 예를 들어, List[] graph = new ArrayList[N+1]; 형태로 선언하고, 각 노드에 연결된 정점을 리스트에 추가하는 방식

✅ 인접 리스트를 쓰면 좋은 경우

1. 메모리 절약

• 인접 행렬은 O(N^2)의 공간을 사용하지만, 인접 리스트는 O(N + M) 정도의 공간만 사용
• 즉, 희소 그래프(Sparse Graph) 같은 경우, 즉 간선이 적은 그래프에서 효과적

2. 빠른 탐색 (특정 상황에서)

• 특정 노드와 연결된 노드를 찾는 연산이 O(N) → O(노드의 연결 개수)로 줄어듦

전체코드

import java.io.*;
import java.util.*;

public class BOJ_1260 {

    static int N; // N : 정점의 개수
    static int M; // M : 간선의 개수
    static int V; // V : 탐색을 시작할 정점의 번호
    static int[][] map;
    static int[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        map = new int[N + 1][N + 1];

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            map[v1][v2] = 1;
            map[v2][v1] = 1;
        }
        visited = new int[N + 1];
        dfs(V);
        System.out.println();
        visited = new int[N + 1];
        bfs(V);
    }

    public static void dfs(int v) {
        visited[v] = 1;
        System.out.print(v + " ");

        for(int i = 1; i <= N; i++){
            if(map[v][i] == 1 && visited[i] == 0){
                dfs(i);
            }
        }
    }

    public static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        visited[v] = 1;

        while(!queue.isEmpty()){
            int current = queue.poll();
            System.out.print(current + " ");
            visited[current] = 1;
            for(int i = 1; i <= N; i++){
                if(map[i][current] == 1 && visited[i] == 0){
                    queue.offer(i);
                    visited[i] = 1;
                }
            }
        }
    }
}

느낀점

• BFS, DFS 꾸준히 연습해야함 !!
• 인접리스트로도 구현해보자 !!