bfs_dfs

BFS & DFS

• 추천 문제 - BFS
  • [BOJ] 전쟁 - 전투 (소스코드) - 단순한 영역 개수 세기 문제 1 (y, x)
  • [BOJ] Counting Sheep (소스코드) - 단순한 영역 개수 세기 문제 2 (y, x)
  • [BOJ] 쉬운 최단거리 (소스코드) - 단순한 영역 개수 세기 문제 3 (y, x)
  • [BOJ] 와드 (소스코드) - 단순한 영역 개수 세기 문제 4 (y, x)
  • [BOJ] 경쟁적 전염 (소스코드) - 단계 별 BFS 순회 1 (y, x)
  • [BOJ] 점프 게임 (소스코드) - 단계 별 BFS 순회 2
  • [BOJ] 구슬 탈출 2 (소스코드) - 한 칸 이동이 아닌 경우 + 단계 별 BFS 순회 (y, x)
  • [BOJ] 미로 탐색 (소스코드) - int 벡터를 사용한 BFS 최단경로 문제
  • [BOJ] koze (소스코드) - bool 벡터를 사용한 BFS 기본 응용문제
  • [BOJ] 영역 구하기 (소스코드) - 2차원 평면 상에 분리되어 있는 영역의 수와 크기 구하기
  • [BOJ] 토마토 (소스코드) - 최단경로 문제 응용 (이동 불가능한 조건)
  • [BOJ] Elevator Trouble (소스코드) - 1차원 BFS 최단경로 문회
  • [BOJ] 벽 부수고 이동하기 4 (소스코드) - 영역 수를 미리 계산해 시간복잡도 줄이기

---

• 추천 문제 - DFS
  • [BOJ] 바이러스 (소스코드) - 재귀를 이용한 DFS
  • [BOJ] 물통 (소스코드) - 재귀를 이용한 DFS + 구현 1
  • [BOJ] 월드컵 (소스코드) - 재귀를 이용한 DFS + 구현 2
    • 재귀에서 비용이 발생하는 지역변수들(예: vector)는 static을 사용하거나 재귀에서만 접근 가능한 전역변수로 선언할 것:
      • 재귀 내에 벡터를 지역변수로 선언한 경우(시간초과) (소스코드)
      • 재귀 내에 벡터를 static변수로 선언한 경우(492 ms) (소스코드)
      • 벡터를 재귀에서만 접근 가능하도록 선언한 경우(428 ms) (소스코드)
    • 제한시간이 짧은 경우 비용이 큰 방법을 다른 방법으로 대체해야 함(vector -> 일반 배열 등)

---

• 추천 문제 - 백트래킹
  • [BOJ] Back to the Barn (소스코드) - 단순한 백트래킹 + 영역탐색
  • [BOJ] N-Queen (소스코드) - 백트래킹 + 구현 1
  • [BOJ] 비숍 (소스코드) - 백트래킹 - 구현 2
  • [BOJ] Sudoku (소스코드) - 백트래킹 - 구현 3
  • [BOJ] Letters (소스코드) - 백트래킹 + 영역 탐색

---

BFS(Breadth-first search)

• 가중치가 없는 최단 경로 문제 풀이에는 BFS를 사용해야 함
• 시작 정점으로부터 근접한 정점 우선 방문
• queue 사용

BFS 동작

• 시작 정점을 queue에 넣고, 방문했음을 기록
• queue가 전부 비워질 때까지 아래 동작 반복:

1. queue로부터 정점 하나를 가져옴
2. 정점의 근접 정점 조사:
3. 해당 정점이 범위를 벗어난다면, 그대로 조사 종료
4. 해당 정점이 방문 상태라면, 그대로 조사 종료
5. 해당 정점이 방문 전 상태라면, 해당 정점을 queue에 넣음과 동시에 방문했음을 기록

• 모든 정점이 queue에 한 번씩 들어가므로, 정점이 N개일 때의 시간 복잡도는 O(N)

BFS 특징

• 주어진 모든 정점 순회 (flood fill 문제 해결 가능)
• 시작 정점과 종료 정점 간 최단 경로 계산 가능
• BFS는 모든 정점이 인접한 정점과의 거리 차가 1임을 보장
• queue에 입력되는 정점은 시작 정점으로부터 거리 순임을 보장

연습문제

• [BOJ] 그림 (소스코드) - BFS 사용

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

int main() {
  int r, c;
  std::cin >> r >> c;
  std::vector<std::vector<int>> v(r + 1, std::vector<int>(c + 1));
  for (int i = 1; i <= r; ++i) {
    for (int j = 1; j <= c; ++j)
      std::cin >> v[i][j];
  }

  std::vector<std::vector<bool>> is_visited(r + 1, std::vector<bool>(c + 1));
  std::vector<int> areas;
  for (int i = 1; i <= r; ++i) {
    for (int j = 1; j <= c; ++j) {
      if (is_visited[i][j] || !v[i][j])
        continue;

      int area = 0;
      std::queue<std::pair<int, int>> q;
      q.push({i, j});
      is_visited[i][j] = true;
      while (!q.empty()) {
        ++area;
        auto cur = q.front();
        q.pop();

        // horizontally, vertically
        const std::vector<std::pair<int, int>> kAdj = {
          {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (const auto& d : kAdj) {
          int y = cur.first + d.first;
          int x = cur.second + d.second;

          if (y < 1 || y > r)
            continue;
          if (x < 1 || x > c)
            continue;
          if (is_visited[y][x] || !v[y][x])
            continue;
          q.push({y, x});
          is_visited[y][x] = true;
        }
      }
      areas.push_back(area);
    }
  }
  std::sort(areas.begin(), areas.end());
  std::cout << areas.size() << '\n' << ((!areas.empty()) ? areas.back() : 0);

  return 0;
}

---

DFS(Depth-first search)

• 시작 정점으로부터 해당 분기 우선 방문
• stack 또는 재귀함수 사용

DFS 동작

• 시작 정점을 stack에 넣고, 방문했음을 기록
• stack이 전부 비워질 때까지 아래 동작 반복:

1. stack으로부터 정점 하나를 가져옴
2. 정점의 근접 조사:
3. 해당 정점이 범위를 벗어난다면, 그대로 종료
4. 해당 정점이 방문 상태라면, 그대로 조사 종료
5. 해당 정점이 방문 전 상태라면, 해당 정점을 stack에 넣음과 동시에 방문했음을 기록

• 모든 정점이 stack에 한 번씩 들어가므로, 정점이 N개일 때의 시간 복잡도는 O(N)

DFS 특징

• 주어진 모든 정점 순회 (flood fill 문제 해결 가능)
• 시작 정점과 종료 정점 간 최단 경로 계산 불가
• BFS는 모든 정점이 인접한 정점과의 거리 차가 1임을 보장하지 않음
• 다차원 배열에서의 flood fill은 BFS, DFS 둘 다 가능하지만, 다차원 배열에서의 최단경로 찾기는 BFS만 가능하므로, 다차원 배열에서의 순회 문제는 주로 BFS만 사용됨

연습문제

• [BOJ] DFS와 BFS (소스코드) - DFS(stack) 사용

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <utility>

void Dfs(int n, int v);
void Bfs(int n, int v);

std::vector<std::vector<int>> g;
std::vector<bool> is_visited;

int main() {
  int n, m, v;
  std::cin >> n >> m >> v;
  g = std::vector<std::vector<int>>(n + 1, std::vector<int>(n + 1));
  while (m--) {
    int x, y;
    std::cin >> x >> y;
    g[x][y] = g[y][x] = 1;
  }

  Dfs(n, v);
  std::cout << '\n';
  Bfs(n, v);

  return 0;
}

void Dfs(int n, int v) {
  std::stack<int> s;
  s.push(v);
  is_visited = std::vector<bool>(n + 1);
  while (!s.empty()) {
    auto cur = s.top();
    s.pop();

    if (is_visited[cur])
      continue;
    is_visited[cur] = true;
    std::cout << cur << ' ';
    // NOTICE: Search in reverse order considering the characteristics of the
    //         stack
    for (int i = n; i > 0; --i) {
      if (is_visited[i])
        continue;
      if (!g[cur][i])
        continue;
      s.push(i);
    }
  }

  return;
}

void Bfs(int n, int v) {
  std::queue<int> q;
  q.push(v);
  is_visited = std::vector<bool>(n + 1);
  is_visited[v] = true;
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();

    std::cout << cur << ' ';
    for (int i = 1; i <= n; ++i) {
      if (is_visited[i])
        continue;
      if (!g[cur][i])
        continue;
      q.push(i);
      is_visited[i] = true;
    }
  }

  return;
}

• [BOJ] DFS와 BFS (소스코드) - DFS(recursion) 사용

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

void Dfs(int n, int v);

std::vector<std::vector<int>> g;
std::vector<bool> is_visited;

int main() {
  int n, m, v;
  std::cin >> n >> m >> v;
  g = std::vector<std::vector<int>>(n + 1, std::vector<int>(n + 1));
  while (m--) {
    int x, y;
    std::cin >> x >> y;
    g[x][y] = g[y][x] = 1;
  }

  // dfs
  is_visited = std::vector<bool>(n + 1);
  Dfs(n, v);
  std::cout << '\n';

  // bfs
  std::queue<int> q;
  q.push(v);
  is_visited = std::vector<bool>(n + 1);
  is_visited[v] = true;
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();

    std::cout << cur << ' ';
    for (int i = 1; i <= n; ++i) {
      if (is_visited[i])
        continue;
      if (!g[cur][i])
        continue;
      q.push(i);
      is_visited[i] = true;
    }
  }

  return 0;
}

void Dfs(int n, int v) {
  is_visited[v] = true;
  std::cout << v << ' ';
  for (int i = 1; i <= n; ++i) {
    if (is_visited[i])
      continue;
    if (!g[v][i])
      continue;
    Dfs(n, i);
  }

  return;
}

Backtracking

• DFS(재귀)의 응용
• Go as deeply as possible, backtrack if impossible

Backtracking과 DFS 차이

• 백트래킹: 탐색 중 후보해가 될 수 없는 경우(if impossible), 이전 단계로 돌아와 다른 후보해 탐색
• DFS: 모든 노드를 방문

연습문제

• [BOJ] N과 M (1) (소스코드)

#include <iostream>
#include <vector>

void Bt(int);

std::vector<int> arr;
std::vector<bool> is_visited;
int n, m;

int main() {
  std::cin >> n >> m;
  arr = std::vector<int>(n + 1);
  is_visited = std::vector<bool>(n + 1);
  Bt(0);

  return 0;
}

void Bt(int s) {
  if (s == m) {
    for (int i = 0; i < m; ++i)
      std::cout << arr[i] << ' ';
    std::cout <<'\n';

    return;
  }
  for (int i = 1; i <= n; ++i) {
    if (is_visited[i])
      continue;

    arr[s] = i;
    // Go as deeply as possible, backtrack if impossible
    is_visited[i] = true;
    Bt(s + 1);
    is_visited[i] = false;
  }

  return;
}

---

이전 - STL - Container Classes:	목록	다음 - Recursion