백준 1260번

1260번: DFS와 BFS

DFS와 BFS의 개념을 알아가고자 푼문제이다. 자료구조 수업시간에 배우기는 했지만 1년 정도 지나서 까먹었었고

C언어로 배워가지고 자바로는 어떻게 구현하는지 몰라서 개념을 알아가고자 구글링을 참고했고 정리해야겠다.

---

DFS(깊이 우선 탐색법)

 

DFS란 깊이 우선탐색이라고 하며 깊은 곳 우선으로 탐색하여 최종적으로 연결된 모든 정점을 탐색하는 방법이다.

자바에서는 스택이나 재귀호출 방식으로 구현을 한다.

전위 순환을 포함한 다른 형태의 트리 순회는 모두 DFS의 한종류이다.

 

---

BFS(너비 우선 탐색)

너비를 우선으로 탐색하는 그래프 탐색이다. 그 말은 깊이가 1인 모든 노드를 방문하고 그다음 깊이가 2인 노드, 그다음 3인 노드를 

방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

재귀적으로 동작하지 않으며 큐를 이용해 구현하고 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선택한다.

---

인접행렬

 

그래프의 연결 관계를 이차원 배열로 나타내는 방식이다.

예를 들어 arr [1][2]의 배열에 1의 값이 들어가 있다면 1과 2 노드가 연결관계를 맺고 있다는 의미가 된다.

---

구현.

public class Main
{
    static int [][] arr;
    static boolean [] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int v = sc.nextInt();

        arr = new int[n+1][n+1];

        for(int i = 0;i<m;++i)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();

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

인접행렬의 형태로 데이터가 주어지기 때문에 반복문을 이용해 arr의 배열에다가 값을 넣어준다.

그리고 노드에 방문을 했는지 하지 않았는지 체크하기 위해 boolean type의 visited배열도 선언해 준다.

 

 

 

예제 2번 그래프 모양

 

private static void dfs(int v)
{
    visited[v] = true;
    System.out.printf(v+" ");


    for(int j = 1;j<arr.length;++j)
    {
        if(arr[v][j] == 1 && visited[j]==false)
        {
            dfs(j);
        }
    }
}

DFS는 스택과 재귀를 이용해 구현할 수 있는대 재귀함수를 이용해 구현하였다.

처음에 정점의 번호 v가 들어오면 v는 방문을 했으니 visited [v] 값을 true로 바꿔준다.

 

반복문을 이제 이용해 v와 인접한 정점을 탐색한다.

v가 만약 3이라고 가정하면 5와 인접한 정점을 우리가 초기에 반복문을 이용해 arr배열에 넣어 두었다

arr [3][1] ==1이라면 5와 3이 인접해잇 다고 볼 수 있고 visited [1] == false라면 아직 정점 1에는 방문하지 않았다는 것을 알 수 있다.

그러면 이제 정점 1의 인접한 정점과 정점 1을 방문했다고 체크해야 하기 때문에 dfs함수의 매개변수에 1을 넘겨주어 

1과 인접했고 아직 방문하지 않은 정점(2)을 탐색해 재귀 호출 해나가면서 DFS탐색을 해나간다.

 

private static void bfs(int v)
{
    Queue<Integer>queue = new LinkedList<>();
    queue.offer(v);
    visited[v] = true;

    System.out.printf(v+" ");

    while(!queue.isEmpty())
    {
        int n = queue.poll();

        for(int i  =1;i<arr.length;++i)
        {
            if(arr[n][i] ==1 && visited[i]==false)
            {
                visited[i] = true;
                System.out.printf(i + " ");
                queue.offer(i);
            }
        }
    }
}

깊이우선 탐색법 코드이다

큐를 이용해 구현하는 방식을 볼 수 있다. 

탐색을 시작할 정점의 번호가 3이면 넓이 우선탐색이니까 3과 인접한 1,4를 탐색해야 한다. 코드를 한번 보자

 

탐색을 시작할 정점 v(3)이 들어오면 queue에 3을 넣어준다. 그리고 visited [3] = true값을 넣어줘어 3에 방문했다고 체크한다.

다음은 3과 인접한 정점을 찾기 위해 큐에서 3을 꺼내서 n에 담아준다.

반복문을 돌면서 3과 인접하였고 방문하지 않은 값을 찾아낸다.

예제 그래프대로라면 arr [3][1], arr [3][4]가 인접하였고 아직 방문하지 않았다. 그렇다면 visited [1], visited [4]의 값은 true로 바뀌고

1,4를 queue에 넣어준다. 이렇게 되면 3과 인접한 정점을 찾는 과정은 끝이 난다.

 

다음은 현재 queue의 head가 1이기 때문에 1과 인접한 정점을 찾아낸다. 예시에서는 arr [1][2]가 될 것이다. 

이렇게 큐 head의 값에 인접한 정점을 찾는 과정을 반복하면서 bfs탐색을 해나간다.

---

전체 코드

import java.util.*;
public class Main
{
    static int [][] arr;
    static boolean [] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int v = sc.nextInt();

        arr = new int[n+1][n+1];

        for(int i = 0;i<m;++i)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
			
            //인접행렬에 값 세팅.
            arr[a][b] = 1;
            arr[b][a] = 1;
        }


        visited = new boolean[n+1];
        dfs(v);

        System.out.println();

        visited = new boolean[n+1];
        bfs(v);
    }

    private static void dfs(int v)
    {
        visited[v] = true;
        System.out.printf(v+" ");


        for(int j = 1;j<arr.length;++j)
        {
            if(arr[v][j] == 1 && visited[j]==false)
            {
                dfs(j);
            }
        }
    }

    private static void bfs(int v)
    {
        Queue<Integer>queue = new LinkedList<>();
        queue.offer(v);
        visited[v] = true;

        System.out.printf(v+" ");

        while(!queue.isEmpty())
        {
            int n = queue.poll();

            for(int i  =1;i<arr.length;++i)
            {
                if(arr[n][i] ==1 && visited[i]==false)
                {
                    visited[i] = true;
                    System.out.printf(i + " ");
                    queue.offer(i);
                }
            }
        }
    }


}

논리적으로 많은 생각을 하게 하는 알고리즘인 것 같다. 빨리 후다닥 공부 더해야겟다!