(JAVA) 백준 1260번 : DFS와 BFS

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

문제

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

입력

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

출력

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

---

주어진 그래프를 DFS와 BFS로 수행한 결과를 출력하는 문제.

생소한 개념이어서 시행착오가 많았기에 푸는 과정을 정리하려고 한다.

 

먼저 그래프는 정점이 서로 이어진 형태로, 이어진(서로 참조할 수 있는) 길을 간선이라고 한다.

구현은 중첩 리스트(이차원 배열 등)으로 할 수 있다. 

예를 들어, 1과 2,3,4 5와 6,7이 서로 이어진 상태라면 

list[1] = [2,3,4]

list[2] = [1]

list[3] = [1]

list[4] = [1]

list[5] = [6,7]

list[6] = [5]

list[7] = [5]

의 방식으로 각 정점에 방문했을 때 정점에 만들어진 리스트를 통해 다른 정점에 접근할 수 있게 한다.

 

이차원 배열의 형식으로 구현할 수도 있지만, 문제에서는 방문할 수 있는 정점의 갯수가 여러개일 때, 

정점 번호가 작은 것을 먼저 방문하도록 요구했으므로

ArrayList 컬렉션 안에 TreeSet을 만드는 방식으로 그래프를 구현했다.

ArrayList<TreeSet<Integer>> graph = new ArrayList<TreeSet<Integer>>();

만약, 이차원 배열 방식으로 구현했을 시에는, 따로 정렬을 하지 않으면 입력된 순으로 정점을 방문할 수밖에 없다.

 

그래프를 만든 후, 문제에서 요구하는 정점의 갯수만큼 반복문을 통해 정점을 만들어준다. 

for (int i=0;i<N+1;i++){
            graph.add(new TreeSet<Integer>());
        }

 

문제에서는 서로 이어야 할 정점 X, Y를 한 줄씩 X Y 형식으로 입력받기 때문에, 입력받는 문자열을 잘라 배열을 만들고,

정수로 변환하여 그래프 안에 넣었다.

String[] data2 = br.readLine().split(" ");
graph.get(Integer.parseInt(data2[0])).add(Integer.parseInt(data2[1]));
graph.get(Integer.parseInt(data2[1])).add(Integer.parseInt(data2[0]));

이런 방식으로, ArrayList 안에 TreeSet으로 각 정점에서 접근할 수 있는 다른 정점을 입력한다.

이렇게 주어진 정점과 간선으로 만들어진 그래프를 구현한다.

 

이후 함수를 통해 DFS와 BFS를 구현한다.

public static void DFS(int V, ArrayList<TreeSet<Integer>> graph, boolean[] visited) throws IOException {
        visited[V] = true;
        bw.append(V+" ");
        Iterator<Integer> it = graph.get(V).iterator();
        while(it.hasNext()){
            int x = it.next();
            if(!visited[x]){
                DFS(x,graph,visited);
            }
        }        
    }

먼저 DFS는 순회를 시작하는 정점 V와 그래프인 graph, 방문 여부를 확힌할 수 있는 boolean형 visited 배열을 매개변수로 받는다. boolean형 배열은 메인 메소드에서 정점의 갯수+1만큼(배열의 인덱스가 0으로 시작하므로) 만든다.

매개변수를 입력받은 후 시작하는 정점 V를 방문 처리한다. (boolean형 배열에서 방문은 true, 미방문은 false)

이후 방문한 정점을 출력하고 정점에 이어진 다른 정점(TreeSet으로 구현된)을 Iterator를 통해 하나씩 순회한다.

새로 방문할 정점을 x라는 변수에 담고 그 x가 방문되었는지 visited 배열을 통해 확인하고, 

방문하지 않았을시 다시 DFS 함수를 재귀적으로 호출해 DFS를 수행한다.

 

public static void BFS(int V, ArrayList<TreeSet<Integer>> graph, boolean[] visitedd) throws IOException {
        visitedd[V] = true;
        Queue<Integer> que = new LinkedList<>();
        que.offer(V);
        while(!que.isEmpty()){
            int x = que.poll();
            bw.append(x+" ");
            Iterator<Integer> it = graph.get(x).iterator();
            while(it.hasNext()){
                int y = it.next();
                if(!visitedd[y]){
                    que.offer(y);
                    visitedd[y] = true;
                }
            }          
        }
    }

BFS는 DFS와 같은 매개변수를 받는다. 문제에서는 DFS와 BFS를 모두 수행한 결과를 출력하기 때문에, 

방문 여부를 다른 visitedd라는 배열을 통해 처리했다. 

DFS와 동일하게 매개변수를 입력받은 후 시작하는 정점 V를 방문 처리한다.

BFS는 간선을 쭉 타고 들어가는 DFS와 달리, 먼저 방문된 정점에 이어진 다른 정점을 모두 순회한 후에, 다시 이어진 정점에 이어진 정점을 모두 순회한다.

이러한 BFS의 탐색 방식은 큐를 통해 구현한다. 먼저 시작하는 정점을 큐에 집어넣는다.

이후 집어넣은 정점을 다시 뽑고 변수 x에 담고 출력한다. 

변수 x를 통해 정점에 이어진 다른 정점(TreeSet)을 Iterator 형식으로 하나씩 순회한다. 

하나씩 순회하면서 순회한 정점을 변수 y에 담고, visitedd배열을 통해 방문 여부를 확인한다.

방문하지 않았을시, 변수를 다시 큐에 집어넣어 x의  TreeSet 순회가 끝난 이후 y를 출력할 수 있게 하고, 방문 처리한다.

이 과정을 큐가 빌 때까지(모두 방문해서 큐에 집어넣을 정점이 없을 때까지) 수행한다.

 

전체 소스코드

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

public class B_1260 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        ArrayList<TreeSet<Integer>> graph = new ArrayList<TreeSet<Integer>>();
        String[] data = br.readLine().split(" ");
        int N = Integer.parseInt(data[0]);
        int M = Integer.parseInt(data[1]);
        int V = Integer.parseInt(data[2]);
        boolean[] visited = new boolean[N+1];
        boolean[] visitedd = new boolean[N+1];
        for (int i=0;i<N+1;i++){
            graph.add(new TreeSet<Integer>());
        }
        for (int i=0;i<M;i++){
            String[] data2 = br.readLine().split(" ");
            graph.get(Integer.parseInt(data2[0])).add(Integer.parseInt(data2[1]));
            graph.get(Integer.parseInt(data2[1])).add(Integer.parseInt(data2[0]));              
        }
        DFS(V, graph, visited);
        bw.newLine();
        BFS(V, graph, visitedd);
        bw.flush();
        
    }
    public static void DFS(int V, ArrayList<TreeSet<Integer>> graph, boolean[] visited) throws IOException {
        visited[V] = true;
        bw.append(V+" ");
        Iterator<Integer> it = graph.get(V).iterator();
        while(it.hasNext()){
            int x = it.next();
            if(!visited[x]){
                DFS(x,graph,visited);
            }
        }        
    }
    public static void BFS(int V, ArrayList<TreeSet<Integer>> graph, boolean[] visitedd) throws IOException {
        visitedd[V] = true;
        Queue<Integer> que = new LinkedList<>();
        que.offer(V);
        while(!que.isEmpty()){
            int x = que.poll();
            bw.append(x+" ");
            Iterator<Integer> it = graph.get(x).iterator();
            while(it.hasNext()){
                int y = it.next();
                if(!visitedd[y]){
                    que.offer(y);
                    visitedd[y] = true;
                }
            }          
        }
    }
}