230715 Today I Learned

노트북 문제는 어제 밤에 겨우겨우 해결했다. 속도는 느린데 작업관리자로 확인하면 cpu나 메모리나 큰 문제가 안보였다. 그리고 팬 소음이 들려야 되는데 안들렸다. 혹시나해서 노트북 밑판을 열어보니 춘복이 털이 한움큼.. 주기적으로 노트북 청소 해야겠다..
오늘 TIL은 어제 하려다 못했던 BFS 정리!

너비 우선 탐색(BFS)

Breadth First Search. 루트노드에서 시작해 깊이가 같은 노드를 모두 방문해 한 단계씩 더 깊은 노드로 방문해가는 방식.

• 모든 분기점을 다 검사하면서 진행하는 방식

• 큐를 써서 구현한다.

• 이미 지나간 곳을 체크하면서 중복순회하지 않도록 해야한다.

• DFS와 달리 재귀적으로 동작하지 않는다.

• DFS로 수행하기 힘든 깊이가 무한인 경우같은 케이스를 잘 풀수 있지만 공간복잡도가 지수 스케일로 커지기 때문에 조심해야 한다.

Java로 구현 - 큐

public class A_BfsQ {
  // 노드에 방문한 기록을 boolean 배열로 표현. 0번 노드는 제외한다.
  private static boolean[] checked = new boolean[11];
  // 노드가 연결된 정보를 2차원 배열로 표현
  private static int[][] graph = {{},
      {2,3,4},
      {1,5,7},
      {1,6},
      {1,8},
      {2,9},
      {3,8},
      {2,9},
      {4,6},
      {5,7,10},
      {9}
  };

  public static void bfs(int v){
    // 시작 노드 방문 체크
    checked[v] = true;
    // bfs에 사용할 큐 생성
    Queue<Integer> queue = new LinkedList<>();
    // 시작 노드 큐에 삽입
    queue.add(v);
    // 큐가 빌 때 까지 while문 반복
    while(!queue.isEmpty()){
      // 큐에 있는 노드 꺼내서 방문
      int tmp = queue.poll();
      System.out.println(tmp + "번 노드를 탐색합니다.");

      // tmp의 인접 노드들 중 방문하지 않은 노드들 방문하면서 큐에 삽입
      for (int i : graph[tmp]){
        if(!checked[i]){
          queue.add(i);
          checked[i] = true;
        }
      }
    }
  }

  public static void main(String[] args) {
    int start = 1; // 시작노드
    bfs(start);
  }

}

• dfs와는 방문 순서가 달라진 것을 볼 수 있다.