[1260] BFS, DFS

DFS의 경우 깊이 우선 탐색이고

BFS의 경우 너비 우선 탐색인건 다들 알 것이다.

1260 번 문제는 이런 DFS와 BFS의 탐색순서를 출력하는 문제이다.

 

1260 - DFS와 BFS

boj 1260

위 그림과 같이 

정점의 개수, 간선의 개수, 정점의 시작번호(루트번호) 를 첫 줄에 입력받는다.

이후 간선의 개수 만큼 간선들을 입력한다.

 

이후 DFS, BFS를 수행한 결과를 출력하면 되는 문제이다.

 

Main

public class Main {
    public static boolean[] visited = new boolean[1001];
    //DFS위한 방문여부 체크 boolean 배열
    public static boolean[] visited_B = new boolean[1001];
    //BFS위한 방문여부 체크 boolean 배열
    public static Queue<Integer>queue = new LinkedList<Integer>();
    //BFS사용을 위한 정수 큐 선언
    public static int[][] g = new int[1001][1001];
    //간선을 저장할 배열 선언
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(sc.nextLine());
        int N; int M; int V;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        for(int i=0;i<M;i++){
            int a = Integer.parseInt(sc.next());
            int b = Integer.parseInt(sc.next());
            g[a][b] = 1; g[b][a] = 1;
            //간선은 중복 선언해주었다. (1, 2)가 입력될 경우 (2, 1) 도 강제 입력함.
        }
        DFS(V);
        System.out.print("\n");
        BFS(V);
    }
    public static void DFS(int index){...}
    public static void BFS(int index){...}
}

 

DFS

https://developer-mac.tistory.com/64

DFS의 특징들을 정리해보자.

1. 본인의 부모 노드는 항상 방문된 상태이다.

2. 즉, 자식노드로만 향하면 된다.

3. 더 이상 자식노드가 없을 경우 최근접 정점중 방문하지 않은 정점을 방문하면 된다.

 

재귀를 활용해 해결했다.

public static void DFS(int index){
    System.out.print(index+" ");
    visited[index] = true;
    for(int i=1;i<=1000;i++){
        if(g[index][i]==1 && !visited[i])
            DFS(i);
    }
}

1. 2차원 배열을 g를 선언해 간선을 저장했다.

2. 배열 visited를 선언해 방문한 정점을 나타내 주었다. 

3. 해당 정점을 방문하지 않고,기존 정점에서 해당 정점으로 향하는 간선이 존재하면 그 정점에 대해 DFS를 진행하는 방식이다.

 

 

BFS

https://developer-mac.tistory.com/64

BFS의 특징 역시 정리해보자.

1. 깊이 별로 나누어 탐색한다.

2. 깊이에 순위를 매길 경우 루트 기준 깊이 1, 깊이2, 깊이3, 인 정점들을 순서대로 탐색한다.

3. 더이상 해당 깊이에 탐색할 정점이 없을 경우 깊이를 한단계 증가시켜서 새로운 깊이에서 탐색한다.

 

public static void BFS(int index){
    queue.add(index);
    while(!queue.isEmpty()){
        for(int i=1;i<=1000;i++){
            if(g[queue.peek()][i]==1 && !visited_B[i]){
                queue.add(i);
                visited_B[i] = true;
                g[queue.peek()][i] = 0; g[i][queue.peek()] = 0;
            }
        }
        System.out.print(queue.poll()+" ");
    }
}

BFS의 경우 큐를 사용해 해결하였다.

1. 최초 정점(루트)을 큐에 넣는다.

2. 큐에서 모든 정점이 제거 될 때까지 반복문을 진행한다.(모든 정점 탐색이 완료 될 때 까지)

3. 최초 정점(queue peek())과 인접한 정점 중 간선이 존재하고 해당 정점이 방문하지 않은 상태일 때, 해당 정점을 큐에 넣는다.

4. 이후 해당 정점과 인접한 정점에 대해 탐색이 끝났을 경우 해당 정점을 큐에서 제거(poll())함과 동시에 출력한다.

5. 다음 최초 정점, queue peek()를 통한 참조를 통해 위 과정을 반복하여, 큐에서 모든 노드가 제거될 때 까지 진행한다.

 

 

 

언제 사용할 까?

그래프 내 찾으려고 하는 노드의 대략적인 위치를 알 때 루트와 가까우면 BFS, 그렇지 않은면 DFS를 사용하는게 좋을것 같다.