[백준] 1260번 DFS와 BFS 구현해보기 : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/1260

2) 문제

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

3) 입력

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

4) 출력

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

위와 같이 DFS와 BFS 구현 문제를 풀어 볼 것이다. 더 자세한 문제의 제한사항이 궁금하면 위 링크를 클릭하여 들어가보자.

2. DFS BFS

문제를 풀기 전에 아직 DFS와 BFS가 익숙하지 않은 사람들은
https://www.programmingstory.com/2024/02/dfs-bfs.html
위 포스트에서 개념과 구현방식을 다루었으니 살펴보자.

3. 풀이

먼저 DFS (깊이 우선 탐색)부터 코드를 작성해보자


    public static void dfs(int x){
       if (c[x]) return;
        c[x]=true;
        System.out.print(x+" ");
        for(int y: a[x]){
            if (!c[y]){
                dfs(y);
            }
        }
    }

인접리스트의 방법으로 푼 것이다. 가능한 인접리스트 중에서 이미 사용되지 않은 것이 있다면 재귀를 활용해서 dfs 함수를 한 번 더 호출해준다.

다음으로 BFS( 너비 우선 탐색) 코드를 살펴보자


  public static void bfs(int start){
        Queue <Integer> q=new LinkedList<Integer>();
        q.add(start);
        c[start]=true;
        while(!q.isEmpty()){
            int x=q.remove();
            System.out.print(x+" ");
            for(int y: a[x]){
                if (c[y]==false){
                    q.add(y);
                    c[y]=true;
                }
            }
        }
    }

이것은 Queue라는 자료구조를 활용한다.
queue에 인접한 것들을 넣고 하나씩 remove를 하면서 queue에 들어있는 것이 없어질 때까지 탐색을 하는 것이다.

전체 코드를 살펴보면 다음과 같다.


import java.util.*;
public class Main{
    static ArrayList<Integer>[] a;
    static boolean[] c;
        public static void dfs(int x){
       if (c[x]) return;
        c[x]=true;
        System.out.print(x+" ");
        for(int y: a[x]){
            if (!c[y]){
                dfs(y);
            }
        }
    }
    public static void bfs(int start){
        Queue <Integer> q=new LinkedList<Integer>();
        q.add(start);
        c[start]=true;
        while(!q.isEmpty()){
            int x=q.remove();
            System.out.print(x+" ");
            for(int y: a[x]){
                if (c[y]==false){
                    q.add(y);
                    c[y]=true;
                }
            }
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int start=sc.nextInt();
        a=(ArrayList<Integer>[] )new ArrayList[n+1];
        for(int i=1; i<=n;i++){
            a[i]=new ArrayList<Integer>();
        }
        for(int i=0; i<m;i++){
            int from=sc.nextInt();
            int to=sc.nextInt();
            a[from].add(to);
            a[to].add(from);
        }
        for(int i=1; i<=n; i++){
            Collections.sort(a[i]);
        }
        c=new boolean[n+1];
        dfs(start);
        System.out.println();
        c=new boolean[n+1];
        bfs(start);
         System.out.println();
    }
}

인접리스트를 구현할 ArrayList들의 배열 a와 해당 숫자가 사용되었는지를 판단하는 boolean c 배열이 필요하다.
dfs를 한번 시작한 이후에는 c=new boolean[n+1]을 한번 해줌으로써 모든 것을 초기화해주는 작업이 필요하다.