자료구조: 그래프Graph의 기본적인 활용

그래프 graph (3) - 기본적인 활용

그래프의 기본 개념을 설명한 이전 포스팅(개념1, 개념2)에 이은 글입니다. 소개했던 그래프 탐색 방법 두 가지를 실제로 활용하는 법─DFS와 BFS를 java 코드로 구현하는 법에 대해 알아보겠습니다.

깊이 우선 탐색DFS과 넓이 우선 탐색BFS의 주요 구현 방식

---

DFS는 주로 Stack(자료구조)이나 재귀를 통해 구현됩니다.
BFS는 주로 Queue(자료구조)를 이용해 구현됩니다.

DFS는 왜 재귀 || Stack으로 구현?

---

DFS에 대해 공부를 하고 오셨거나 개념에 대한 이전 두 포스팅을 보고 오셨다면 아시겠지만 다시 한 번 정리해서 말해보겠습니다.
깊이 우선 탐색은 끝 조건에 도달할 때까지 계속 반복해서 들어간 후, 끝 조건을 만나면 리턴을 시작해서, 호출한 지점으로 돌아갑니다.
어디서 많이 들어보셨죠? 바로 재귀죠!

• base case에 도달할 때까지(leaf node를 만날 때까지),
• 정해진 방식으로(preorder, inorder, postorder),
• 재귀적으로 호출(하위 요소를 탐색)을 반복하는 것입니다.
  재귀 컨셉에서 이야기 한 적은 없지만 재귀 구조는 반복문이나, 특히 Stack 자료구조로 대치됩니다.
  그래서 'DFS는 Stack이나 재귀로 구현하면 되겠구나!'라고 이해하는 것이죠!

BFS는 왜 Queue로 구현?

---

저번 글에서도 이야기했었지만, BFS는 레벨 순으로 탐색을 접근합니다. 다시 말해, 당장 만난 상위의 요소들부터 하나씩 탐색하고, 그 하위의 요소를 차례로 탐색합니다.

• 먼저 만난 요소를 먼저 탐색하고, 늦게 만난 요소는 먼저 만난 요소들을 다 탐색하고 내보낸 뒤에 탐색합니다.
  BFS의 특징을 말한 위 문장에서 Queue의 특징이 느껴지시나요? FIFO말이에요.
  이런 이유로 BFS를 구현할 때는 주로 Queue 자료구조를 이용하는 것입니다.

코드로 옮겨보기 전에 한 가지 약속

---

방향이 존재하는 경우는 해당하지 않을 수 있지만, 간선이 무향인 경우에는 이런 경우가 존재할 수 있을 것 같습니다.

예를 들어 1 -- 2 -- 3 나란히 연결 된 그래프라고 해볼게요.

1부터 탐색을 시작하기로 했습니다.
1에서 간선을 타고 2로 향했습니다.
2에서 탐색을 이어갑니다.
3...으로 가면 좋겠지만 1로도 간선이 연결되어있네요? 1로 갑니다.
1에서 탐색을 이어갑니다. 간선을 타고 2로 향했습니다.
2에서 탐색을 이어갑니다. 간선을 타고 1로 향했습니다.
1에서 탐색을 이어갑니다. 간선을 타고 2로....
....

이런 일이 일어나지 않기 위해서는, 특별한 목적 없이는 이미 탐색한 노드를 방문하지 않도록 체크해줘야 할 것 같아요.
DFS/BFS 코딩테스트 알고리즘 문제 풀이들을 보면 약속이라도 한 듯이 checked(아니면 visited. 그것도 아니면 marked.)라는 이름의 boolean[] 혹은 int[] 변수가 존재해요. 이 녀석이 바로 그 목적으로 사용되는 변수입니다.
각 정점을 인덱스로 가지면서, 아직 방문하지 않은 경우는 false로 표시하고, 방문과 동시에 true로 값을 바꿔줌으로써 다시 방문하는 일이 없게끔 해요.
물론 필요하지 않아서 사용하지 않을 때도 있지만, 다른 사람의 풀이를 볼 때 checked라는 변수가 나오면 "아~ 걔!" 하고 떠올려주세요.

위 내용이 잘 이해되셨을 것 같지만, 중요하니까 다시 한 번 이야기를 할게요(저는 한번에 이해를 못했어서..ㅠㅜ).

Stack이나 Queue에 한 번 들어갔던 정점은, 다시 들어가지 않게끔 visited 배열을 확인해서, 반드시! 다시 들어가지 않도록 합니다!

무한히 반복될 수 있거나, 탐색한 정점을 다시 방문해서는 안되는 상황이라면... 꼭 위처럼 배열이 아니더라도, 방문여부는 체크를 해야합니다.

DFS(Stack, Recursion), BFS(Queue) java code로 구현

---

아주 기본적인 형태의 구현입니다. 눈에 자주 익혀서 더 복잡한 DFS/BFS의 활용으로 나아가면 좋겠습니다.
카피방지 안되어있으니 복사해서 IDE에 붙여넣고 돌려보시고, 만져보세요!

class GraphSearch {
  int[] vertexs = {0, 1, 2, 3}; //정점들이 존재합니다.
                                  // 편의를 위해서 각 정점은 배열 index와 동일한 데이터를 갖고 있습니다.
  boolean[] visited = new boolean[vertexs.length]; // 방문여부 확인할 배열입니다.
                                            // 부울배열을 생성하면 기본값은 false로 초기화 되어 있습니다.
  int[][] adjacencyMatrix = {
          {0, 1, 1, 1},
          {1, 0, 0, 1},
          {1, 0, 0, 0},
          {1, 1, 0, 0}
  }; // 인접행렬 방식으로 체크할거에요.
      // 인접행렬과 인접리스트의 개념을 알고 싶으시다면 이전 포스팅으로!

  /*
  0 - - - - - 1
  :  *        :
  :     *     :
  :        *  :
  2           3

  이렇게 연결되어 있다는 걸 이해해야 합니다.
  */

  void setting() { //호출하려고 만들어본 메서드. 별 의미 없어요!
      dfs();
      recursiveDfs();
      bfs();
  }

  void dfs() {
      System.out.println("DFS=================================");
      dfs(0); // 시작정점을 호출하는 것으로 시작합니다.
      System.out.println("=================================DFS");
  }
  void dfs(int index) {
      Stack<Integer> stack = new Stack<>(); //스택을 생성합니다.
      stack.push(index); //시작정점을 스택에 push합니다.
      visited[index] = true; //시작정점을 방문했다고 표시하고

      while (!stack.isEmpty()) { // 이제부터 스택에 값이 없을 때까지(모두 탐색하고 스택이 빌때까지) 아래의 탐색을 반복할거에요.

          int nowNode = stack.pop(); // 1. 스택에서 값을 하나 꺼내줍니다.
          for (int m : adjacencyMatrix[nowNode]) { // 2. 꺼낸 스택의 인접정보를 하나씩 확인해서
              if (!visited[m]) { // 3. 아직 방문하지 않았던 인접노드들을 찾고요
                  stack.push(m); // 4. 스택에 넣습니다.
                  visited[m] = true; // 5. 방문대기열에 들어갔으니(곧 방문할거니까) 방문했다고 체크해도 되겠죠?
                                      // 대기열에 있는데 자꾸 순번표 뽑으면 안될거잖아요!ㅎㅎ
              }
          }

          /* 한 정점의 탐색을 마치고 다음 정점으로 넘어가기 전에 출력도 해볼게요. */
          System.out.print(" " + vertexs[index] + " ");
      }
  }

  void recursiveDfs() {
      visited = new boolean[vertexs.length]; //방문배열은 다시 초기화 해줄게요.
      System.out.println("recursiveDFS========================");
      dfs(0); // 시작정점을 호출하는 것으로 시작합니다.
      System.out.println("========================recursiveDFS");
  }
  void recursiveDfs(int vertex) {

      /*
      * 아래 if 조건은 수행될 일이 없어요.
      * 첫째로, 저희는 재귀를 호출하기 전에 방문여부를 확인하기 때문이고,
      * 둘째로, 저희는 인접정점이 있을 때에만 재귀호출하고 있기 때문이죠(이건 어떤 말인지 이해가 안되셔도 괜찮아요)
      *
      * 본래 DFS 재귀의 base case에는, 탐색할 요소의 값이 null인지 체크하는 경우가 많습니다.
      * 현재 정점의 인접정점이 없으면(null) 탐색을 종료하는거죠.
      * 이런식으로, 더이상의 정점이 없을 때에 탐색을 종료한다는 base case를 만들어준다는 것만 기억하심 됩니다.
      * */
      if (vertexs[vertex] == -1 || visited[vertex]) return;

      visited[vertex] = true; // 정점의 방문여부를 true로 바꿔두고요.

      System.out.print(" " + vertexs[vertex] + " "); // 실행할 구문을 작성해줍니다.

      for (int m : adjacencyMatrix[vertex]) { // 그리고 인접한 정점들을 확인해서
          if (!visited[m]) { // 그 중 아직 방문하지 않은 정점부터 차례로 하나씩
              recursiveDfs(m); // 재귀적으로 방문합니다.
          }
      }
  }

  void bfs() {
      visited = new boolean[vertexs.length]; //방문배열은 다시 초기화 해줄게요.
      System.out.println("BFS=================================");
      bfs(0); // 시작정점을 호출하는 것으로 시작합니다.
      System.out.println("=================================BFS");
  }

  void bfs(int index) {
      Queue<Integer> queue = new LinkedList<>(); // 큐를 만들어줍니다.
      queue.add(index); // 시작정점을 큐에 넣어줍니다.
      visited[index] = true; //시작정점의 방문여부를 true로 바꿉니다.

      //그리고 또 반복할건데...
      while (!queue.isEmpty()) { // 탐색을 마치고 큐가 텅텅 빌 때까지요.

          int nowNode = queue.poll(); // 1. 큐에서 값을 하나 꺼내주고요.
          for (int m : adjacencyMatrix[nowNode]) { // 2. 큐에서 꺼낸 정점의 인접정보를 하나씩 확인해서
              if (!visited[m]) { // 3. 아직 방문하지 않았던 인접노드들을 찾고요
                  queue.add(m); // 4. 큐에 넣습니다.
                  visited[m] = true; // 5. 방문대기열에 들어갔으니(곧 방문할거니까) 방문했다고 체크!
              }
          }

          /* 한 정점의 탐색을 마치고 다음 정점으로 넘어가기 전에 출력도 해볼게요. */
          System.out.print(" " + vertexs[index] + " ");
      }
  }
}

마무리

---

많이 낯설고 개념이 와닿지 않을 수 있어요. 하지만 DFS나 BFS나 거의 비슷한 코드인데도 자료구조의 특성 차이만으로 쉽게 구현할 수 있으니까, 포기하지 마시고 천천히 눈에 많이 익혀두면 좋겠습니다. 물론 저도 마찬가지고요. ㅎㅎ

그래프 공부도 수고하셨습니다.