기타 정보/코딩테스트

너비 우선 탐색 (BFS) 정리

Wings of Freedom 2023. 9. 14. 18:35

BFS (너비 우선 검색) 정리

소개

Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다.
Queue를 사용해서 구현한다.

 

시간 복잡도

  • 인접 리스트 : O(V + E)
  • 인접 행렬 : O(V^2)

접점(V), 간선(E)

 

class Graph {
  private int V;
  private LinkedList<Integer> adj[];

  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i)
      adj[i] = new LinkedList();
  }

  void addEdge(int v, int w) { adj[v].add(w); }

  /* BFS */
  void BFS(int s) {
    boolean visited[] = new boolean[V];
    LinkedList<Integer> queue = new LinkedList<Integer>();

    visited[s] = true;
    queue.add(s);

    while (queue.size() != 0) {
      // 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력
      s = queue.poll();
      System.out.print(s + " ");

      // 방문한 노드와 인접한 모든 노드를 가져온다.
      Iterator<Integer> i = adj[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        // 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }
}

위 문제 모두 BFS 기초적인 문제이다.

문제 풀이 요령

BFS를 이용해 해결할 수 있는 문제는 3가지 조건을 만족해야한다.

  1. 최소 비용 문제
  2. 간선의 가중치가 1이다.
  3. 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족한다.)

 

BFS 문제

첫 번째 토마토는 높이는 고려하지 않기 때문에 쉬우나 두번째 토마토 문제는 높이를 고려해야하기 때문에 상당히 까다로워진다.

2019년 라인 하계 인턴문제에 비슷한 유형이 출제되었다.

DP문제로 분류되어 있지만 BFS로 풀 수 있다.

 

출처 : https://developer-mac.tistory.com/78