DFS, BFS๋ฅผ ๊ตฌํ˜„ํ•  ๋•Œ์˜ ๊ฒฝํ—˜๋“ค

3 minute read

๋“ค์–ด๊ฐ€๋ฉฐ

2020-1ํ•™๊ธฐ, ๋Œ€ํ•™์—์„œ โ€˜์•Œ๊ณ ๋ฆฌ์ฆ˜โ€™ ์ˆ˜์—…์„ ๋“ฃ๊ณ  ๊ณต๋ถ€ํ•œ ๋ฐ”๋ฅผ ์ •๋ฆฌํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ์ง€์ ์€ ์–ธ์ œ๋‚˜ ํ™˜์˜์ž…๋‹ˆ๋‹ค :) ์ „์ฒด ํฌ์ŠคํŠธ๋Š” Algorithm ํฌ์ŠคํŠธ์—์„œ ํ™•์ธํ•˜์‹ค ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

<DFS>, <BFS>์— ๋Œ€ํ•œ ๊ธฐ์ดˆ ๋ฐฑ์ค€ ๋ฌธ์ œ์ธ 1260๋ฒˆ - DFS์™€ BFS ๊ธฐ์ค€์œผ๋กœ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•ด๋ณด์•˜๋‹ค.

Set-up

์ €๋Š” ๊ทธ๋ž˜ํ”„์˜ edge $E$๋ฅผ ์ €์žฅํ•  ๋•Œ, โ€œ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ(Adjacency List)โ€ ๋ฐฉ์‹์„ ์„ ํ˜ธ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋Š” bool ํƒ€์ž…์˜ ๋ฐฐ์—ด isVisit[]๋กœ ๊ธฐ๋ก ํ•ฉ๋‹ˆ๋‹ค.

vector<int> edges[MAX];
bool isVisit[MAX];

๊ทธ๋ฆฌ๊ณ  ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๋Š”๊ฑด ์š”๋ ‡๊ฒŒ

for (int i = 0; i < M; i++) {
  int s, e;
  scanf("%d %d", &s, &e);
  edges[s].push_back(e);
  edges[e].push_back(s);
}

DFS

Recursion

void dfs(int v) {
  printf("%d ", v);
  isVisit[v] = true;

  for (int i = 0; i < edges[v].size(); i++) {
    int adj = edges[v][i];
    if (!isVisit[adj]) {
      dfs(adj);
    }
  }
}

Stack

void dfs_stack(int s) {
  stack<int> st;
  st.push(s);

  while (!st.empty()) {
    int top = st.top();
    st.pop();

    if(!isVisit[top]){
      isVisit[top] = true;
      printf("%d ", top);

      for (int i = 0; i < edges[top].size(); i++) {
        int adj = edges[top][i];
        if (!isVisit[adj]) {
          st.push(adj);
        }
      }
    }
  }
}

BFS

void bfs(int s) {
  queue<int> q;
  isVisit[s] = true;
  q.push(s);

  while (!q.empty()) {
    int front = q.front();
    printf("%d ", front, q.size());
    q.pop();

    for (int i = 0; i < edges[front].size(); i++) {
      int adj = edges[front][i];
      if (!isVisit[adj]) {
        q.push(adj);
        isVisit[adj] = true;
      }
    }
  }
}

DFS-BFS ํ˜ธํ™˜ ์ฝ”๋“œ

๋ช‡๋…„ ๊ฐ„์˜ PS ๊ฒฝํ—˜์— ๋”ฐ๋ฅด๋ฉด, <DFS>์˜ ๊ตฌํ˜„ ์ฝ”๋“œ์™€ <BFS>์˜ ๊ตฌํ˜„ ์ฝ”๋“œ์˜ ํ˜•ํƒœ๋ฅผ ๊ฑฐ์˜ ์ผ์น˜์‹œํ‚ฌ ์ˆ˜ ์žˆ๋Š” ๊ตฌํ˜„ ์Šคํƒ€์ผ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์Šคํƒ€์ผ์€ stack์„ ์“ฐ๋ฉด DFS๊ฐ€ ๋˜๊ณ , queue๋ฅผ ์“ฐ๋ฉด BFS๊ฐ€ ๋ฉ๋‹ˆ๋‹ค!

1. DFS (stack)

void dfs_stack(int s) {
  stack<int> st; // stack ์‚ฌ์šฉ
  st.push(s);

  while (!st.empty()) {
    int top = st.top();
    st.pop();

    if(!isVisit[top]){
      isVisit[top] = true;
      printf("%d ", top);

      for (int i = 0; i < edges[top].size(); i++) {
        int adj = edges[top][i];
        if (!isVisit[adj]) {
          st.push(adj);
        }
      }
    }
  }
}

2. BFS (queue)

void bfs_queue(int s) {
  queue<int> q; // queue๋ฅผ ์‚ฌ์š”!
  q.push(s);

  while (!q.empty()) {
    int front = q.front();
    q.pop();

    if(!isVisit[front]){
      isVisit[front] = true;
      printf("%d ", front, q.size());

      for (int i = 0; i < edges[front].size(); i++) {
        int adj = edges[front][i];
        if (!isVisit[adj]) {
          q.push(adj);
        }
      }
    }
  }
}

์ฝ”๋“œ๋ฅผ ์ž˜ ์‚ดํŽด๋ณด๋ฉด, Container๋กœ stack์„ ์„ ํƒํ•˜๋Š”์ง€, queue๋ฅผ ์„ ํƒํ•˜๋Š”์ง€์— ๋”ฐ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋ฐ”๋€๊ฑด ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๊ฐœ์ธ์ ์œผ๋กœ ์ž์ฃผ ์“ฐ๋Š” ์Šคํƒ€์ผ์€ ์•„๋‹Œ๋ฐ, <DFS>, <BFS> ์ฝ”๋“œ๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ๊ตฌํ˜„ํ•ด๋ณด๋‹ˆ ์ด๋Ÿฐ ํŒจํ„ด๋„ ๋ณด์ด๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค ใ…Žใ…Ž ๐Ÿ˜Ž ํ•˜์ง€๋งŒ ์—ฌ์ „ํžˆ <DFS> ๊ตฌํ˜„์€ <์žฌ๊ท€ recursion>์œผ๋กœ ๊ตฌํ˜„ํ•˜๋Š” ๊ฑธ ์„ ํ˜ธํ•˜๋Š” ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค ๐Ÿ˜†

Categories:

Updated: