백준 1260, DFS와 BFS

오늘은 백준의 1260번 문제인 DFS와 BFS문제를 풀어봤는데요,

DFS와 BFS의 개념과 구현, 그리고 인접 행렬과 인접 리스트에 대한 내용을 공부할 수 있는 아주 좋은 문제 같았습니다.

학부 수업에서 자료구조를 들으면서 DFS와 BFS, 그래프에 대해서 짧게 배운적이 있습니다만

구현을 해보고 응용하기엔 너무 얕게 배워서 오늘 이 문제를 풀면서 다시 공부하게 됐었네요.

 

그래프와 인접 행렬, 인접 리스트

DFS, BFS를 들어가기 전에 그래프의 개념에 대해서 알아볼 필요가 있는데요

그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조입니다.

여기서 노드는 경우에 따라서 Vertex로 부르기도 합니다.

그래프는 상당히 큰 개념인데요, 트리라고 불리는 자료구조도 그래프의 일종입니다.

그래프의 간선은 방향이 있는 경우도 있고( A->B ) 방향이 없는 경우도 있습니다.

또 가중치가 있어서 한 Vertex에 이어지는 간선이 여러개 카운트 되는 경우와 아닌 경우가 있습니다.

 

그래프를 구현하기 위해서 보통 두가지 방법을 많이 씁니다. 바로 인접 행렬, 인접 리스트입니다.

 

인접 리스트

인접 리스트는 각각의 정점(Vertex)에 인접한 정점들을 리스트로 나타낸 것입니다.

방향, 가중치가 주어진 그래프를 주로 인접 리스트로 나타내죠.

인접 리스트는 배열과 배열의 각 인덱스마다 존재하는 또 다른 리스트, 연결 리스트 등으로 구현합니다.

 

인접 행렬

인접 행렬은 노드를 2차원 배열로 만든 것입니다. 무방향 그래프에 가중치가 없는 경우 주로 인접행렬로 나타냅니다.

인접 행렬은 정점의 개수가 N인 그래프를 나타내기 위해 N^2의 메모리 공간이 필요합니다.

이는 공간 효율성이 상당히 떨어지는 것으로 알고리즘 문제에서 인접 행렬을 사용할 때 주의를 요합니다.

 

 

저는 여기서 인접 행렬을 이용해 1260번을 풀었습니다.

 

    public static void dfs(int i){
        //방문한 vertex를 true로 나타냅니다.
        visit[i] = true;
        System.out.print(i + " ");
        for (int j=1; j<n+1; j++){
            //인접행렬에서 1인 곳을 찾음과 동시에 해당 vertex가 방문한 적이 없는지 확인합니다.
            if (map[i][j]==1&&visit[j]==false){
                //해당 vertex로 이동해서 다시 탐색합니다.
                dfs(j);
            }
        }
    }

 

먼저 DFS는 재귀를 이용해서 구현했습니다. 방문한 곳의 정점을 true로 표시하고, for문은 행렬의 행을 탐색한다고 생각하면 됩니다. 탐색하다가 방문하지 않은 새로운 정점을 찾으면 해당 정점에서 재귀가 일어나죠. 결과적으로 정점에서 연결된 정점을 찍는다고 생각하면 됩니다. 저는 for문의 반복이 어떻게 실행되는지 잘 그려지지 않았는데요,

직접 숫자를 넣어보고 배열을 추적하다보니 어떻게 변수가 변하는지 그려지더군요

 

    public static void bfs(int i){
        Queue<Integer> queue = new LinkedList<Integer>();
        //해당 vertex를 큐에 넣습니다
        queue.offer(i);
        visit[i] = true;
        while(!queue.isEmpty()){
            int temp = queue.poll();
            System.out.print(temp + " ");
            //해당 vertex와 인접한 vertex를 모두 큐에 넣습니다.
            for (int k = 1; k<=n; k++){
                if (map[temp][k]==1&&visit[k]==false){
                    queue.offer(k);
                    visit[k] = true;
                }
            }
        }

 

BFS는 큐를 이용해서 구현합니다. 한 정점과 연결된 정점들을 인큐하고, 인큐된 정점들을 팝하면서 다시 큐에 방문하지 않은 정점들을 넣는 식이죠.

 

public class Main {
    //인접행렬로 구현합니다.
    static int map[][];
    static boolean[] visit;
    static int n,m,v;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        //연속 입력을 받고 각 입력을 토큰으로 나눕니다.
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());
        map = new int[n+1][n+1];
        visit = new boolean[n+1];
        for (int j=0; j<n+1; j++){
            Arrays.fill(map[j], 0);
        }
        Arrays.fill(visit,false);
        for (int i=0; i<m; i++){
            String edge = br.readLine();
            StringTokenizer st1 = new StringTokenizer(edge, " ");
            int a = Integer.parseInt(st1.nextToken());
            int b = Integer.parseInt(st1.nextToken());
            map[a][b] = 1;
            map[b][a] = 1;
        }
        dfs(v);
        System.out.println();
        Arrays.fill(visit,false);
        bfs(v);
    }

    public static void dfs(int i){
        //방문한 vertex를 true로 나타냅니다.
        visit[i] = true;
        System.out.print(i + " ");
        for (int j=1; j<n+1; j++){
            //인접행렬에서 1인 곳을 찾음과 동시에 해당 vertex가 방문한 적이 없는지 확인합니다.
            if (map[i][j]==1&&visit[j]==false){
                //해당 vertex로 이동해서 다시 탐색합니다.
                dfs(j);
            }
        }
    }

    public static void bfs(int i){
        Queue<Integer> queue = new LinkedList<Integer>();
        //해당 vertex를 큐에 넣습니다
        queue.offer(i);
        visit[i] = true;
        while(!queue.isEmpty()){
            int temp = queue.poll();
            System.out.print(temp + " ");
            //해당 vertex와 인접한 vertex를 모두 큐에 넣습니다.
            for (int k = 1; k<=n; k++){
                if (map[temp][k]==1&&visit[k]==false){
                    queue.offer(k);
                    visit[k] = true;
                }
            }
        }

    }
}

 

 

그래프란 -
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

자료구조 Graph 이해하기 -
https://medium.com/@gwakhyoeun/til-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-graph-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-6f92fd87a0bd

DFS와 BFS 자바 정리 및 해설 -
https://sundries-in-myidea.tistory.com/4