문제

풀이

풀이

그래프 탐색의 유형 두가지 DFS, BFS의 표준 문제이다. 정점과 간선의 정보를 입력받고 DFS 혹은 BFS 탐색 결과를 출력한다.

DFS는 깊이우선탐색(Depth-First Search)로 탐색 노드의 하위노드를 우선적으로 탐색하고 탐색이 끝나면 그 옆의 branch로 이동하여 탐색을 반복하는 방법이다. 깊이를 우선적으로 최하위 노드를 우선적으로 찾아가는 방법이다.

BFS는 너비우선탐색(Breath-First Search)로 상위 노드와 인접한 노드를 우선적으로 탐색하는 방식이다. 최상위 노드와 그와 인접한 노드를 탐색하고 그 후에는 하위 노드들의 인접 노드를 탐색한다.

DFS와 BFS는 추후에 따로 다뤄서 정리해볼 예정이다.

그래프는 보통 자바에서 2차원 배열의 행렬로 구현하거나 연결리스트로 구현한다. 본 문제는 배열의 행렬로 구현하였다.

DFS는 탐색노드의 하위노드를 확인하고 해당 노드를 이전에 방문하지 않았다면 방문하여 해당 노드의 하위노드를 다시 탐색하는 재귀적 방법을 이용한다.

BFS는 큐를 이용해서 구현할 수 있다. 방문할 예정인 노드들을 큐에 삽입한다. 그리고 하나씩 꺼내면서 해당 노드를 방문하고 해당 노드의 하위노드들을 이후에 방문할 예정이기 때문에 큐에 삽입한다. 물론 노드 탐색시에는 방문 여부에 대해서 항상 갱신하고 이전에 방문한 노드라면 탐색을 하지 않는다.

코드

package java_baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class prob1260 {
    static int graph[][];
    static boolean visit[];
    static int N;
    static int M;
    static int V;
    static Queue<Integer> bfsQue;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();
        V = sc.nextInt();

        bfsQue = new LinkedList<>();

        bfsQue.add(V);

        visit = new boolean[N + 1];

        graph = new int[N + 1][N + 1];  //그래프 생성
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j < N; j++) {
                graph[i][j] = 0;
            }
        }
        for (int i = 0; i < M; i++) {   //그래프 입력
            int a = sc.nextInt();
            int b = sc.nextInt();

            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        for (int i = 0; i <= N; i++) {  //방문 정보 초기화
            visit[i] = false;
        }
        DFS(V);
        System.out.println();

        for (int i = 0; i <= N; i++) {  //방문 정보 초기화
            visit[i] = false;
        }
        BFS();
        return;
    }

    public static void DFS(int start) {
        if(!visit[start]){  //방문하지 않았다면 방문
            System.out.print(start + " ");
            visit[start] = true;
            for(int i=1;i<=N;i++){
                if(graph[start][i] == 1){
                    DFS(i); //노드의 하위노드를 탐색
                }
            }
        }else{
            return;
        }
    }

    public static void BFS() {
        int start = bfsQue.poll();
        visit[start] = true;
        System.out.print(start + " ");

        for(int i=1;i<=N;i++){
            if(graph[start][i] == 1 && !visit[i]){
                bfsQue.add(i);
                visit[i] = true;
            }
        }

        if(!bfsQue.isEmpty()){
            BFS();
        }
    }
}

결과

DFS와 BFS는 꽤나 중요한 부분이기 때문에 따로 정리할 예정이다.