[백준] 1260 DFS와 BFS

DFS와 BFS를 공부하고 좋은 예제를 찾아보다가 백준 알고리즘을 찾게되었다.

DFS는 스택을 이용한 방식으로 현 경로상의 노드만을 기억하면 되기때문에 저장공간의 수요가 적다.

목표노드가 깊은 곳에 있는 경우 빨리 구할 수 있다.

BFS는 큐를 이용한 방식이다. 현 노드에서 인접한 노드를 모두 들리면서 탐색하는 방식이다.

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

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

2018/07/24 다시 품

package baekjun;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class baekjun1260_1 {
        
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //입력
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //정점의 개수
        int m = sc.nextInt(); //간선의 개수
        int v = sc.nextInt(); //시작할 정점의 번호
        
        //배열을 1로 초기화
        //정점 간 연결되는 배열의 개수 는 n+1 , 정점 + 1
        int matrix[][] = new int [n+1][n+1];
        for(int i=1; i<=m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            matrix[x][y]=1;
            matrix[y][x]=1;
        }
        
        //DFS and BFS
        int check[] = new int [matrix[0].length];
        System.out.println("matrix[0].length : " + matrix[0].length);
        DFS(matrix, check, v);
        System.out.println("");
        check = new int[matrix[0].length];
        BFS(matrix, check, v);
    }
 
    private static void BFS(int[][] matrix, int[] check, int m) {
        // TODO Auto-generated method stub
        //인접리스트를 사용해 구현시
        //속도 측면에서 좋음
        Queue<Integer> q = new LinkedList<Integer>();
        
        check[m]=1;
        q.add(m);
        
        while(!q.isEmpty()) {
            int node = q.poll();
            System.out.print(node+" ");
            for(int i=0; i<matrix[0].length; i++) {
                if(matrix[node][i]==1 && check[i]==0) {
                check[i]=1;
                q.add(i);
                }
            }
            
        }
        
    }
 
    private static void DFS(int[][] matrix, int[] check, int m) {
        // TODO Auto-generated method stub
        System.out.print(m+" "); //스택에 담긴 노드를 출력하고
        check[m]=1; //방문했으니 1로
        
        for(int i=1; i<matrix[0].length; i++) {
            //길이 있고, 아직 방문하지 않았으면
            if(matrix[m][i]==1 && check[i]==0) {
                //자식노드 호출(재귀함수)
                DFS(matrix, check, i);
            }
        }
    }
 
}