백준 1260번 JAVA

DFS와 BFS

문제

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

입력

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

출력

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

 

DFS와 BFS를 구현하는데에 DFS는 스택이나 재귀함수로 많이 구현하는데

재귀함수가 좀더 간결하게 코드를 짤수 있어 재귀함수로 구현하였다.

출발하는 노드를 출력하고 자식 노드들을 재귀함수로 호출하였다. 

 

출력하고 호출하여야 반대로 출력되지 않는다.

 

BFS는 큐를 이용하여 구현하였다.

시작 노드를 큐에 넣고 시작하여 큐에서 꺼내고 출력 후 자식 노드를 큐에 넣어주고 

또 꺼내서 출력 후 자식노드를 큐에 넣는 것을 반복한다.

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

public class Main {
    static boolean[] visited;
    static int[][] branch;
    static Queue<Integer> queue = new LinkedList<>();
    static int N,M,V;
    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());
        visited = new boolean[N+1];
        branch = new int[N+1][N+1];

        while(M --> 0){
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());

            branch[a][b] = 1;
            branch[b][a] = 1;
        }
        dfs(V);
        System.out.println();
        Arrays.fill(visited, false);
        bfs(V);
    }


    //재귀를 이용해서 구현
    public static void dfs(int node){
        System.out.print(node + " ");
        visited[node] = true;
        for(int i =1 ;i <= N; i++)
        {
            if(branch[node][i] == 1 && visited[i]  == false){
                dfs(i);
            }
        }
    }

    //큐를 이용해서 구현
    public static void bfs(int node){
        queue.offer(node);
        visited[node] = true;

        //큐에서 꺼내서 출력하고 자식 노드들을 넣고
        while(!queue.isEmpty()){
            int tmp = queue.poll();
            System.out.print(tmp + " ");


            for(int i =1; i <= N; i++){
                if(branch[tmp][i] == 1 && visited[i]  == false){
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }



    }
}

BFS에서 출력이 이상하게 되었었는데 branch설정을 단방향으로만 설정해주었었다....

이것 때문에 뭐가 문젠가 하며 15분정도 고민했다...

 

BFS를 실행하기 전에 Array.fill()로 방문 배열을 초기화를 해주었다.