코테 공부 07.07

오랜만에 개념 공부(복기)...

• 그 전까지는 문제풀이를 했었다

---

DFS

Pseudo Code

DFS(u, adj)
        u.visited = true
        for each v ∈ adj[u]
                if v.visited == false
                        DFS(v, adj)

 

 

구현 방법1: 돌다리를 두들겨 보다.

void DFS(int here) {
        visited[here] = 1;
        for(int there : adj[here]) {
                if(visited[there]) continue;
                DFS(there);
        }
}

 

 

구현 방법2: 못 먹어도 GO

void DFS(int here) {
        if(visited[here]) return;
        visited[here] = 1;
        for(int there : adj[here]) {
                DFS(there);
        }
}

 

 

예제

#include <iostream>

using namespace std;

int MAP[101][101];
bool visited[101][101];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int ans;
int m, n, ny, nx;

void DFS(int y, int x) {
  visited[y][x] = 1;
  for (int i = 0; i < 4; i++) {
    ny = y + dy[i];
    nx = x + dx[i];
    if (ny < 0 || nx < 0 || ny >= n || nx >= m) {
      continue;
    }
    if (MAP[ny][nx] == 1 && !visited[ny][nx]) {
      DFS(ny, nx);
    }
  }
  return;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> MAP[i][j];
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (MAP[i][j] == 1 && !visited[i][j]) {
        ans++;
        DFS(i, j);
      }
    }
  }
  cout << ans << "\n";
  return 0;
}

---

BFS

Pseudo Code

BFS(G, u)
        u.visited = true
        q.push(u);
        while(q.size())
                u = q.front()
                q.pop()
                for each v ∈ G.Adj[u]
                        if v.visited == false
                                v.visited = true
                                q.push(v)

BFS(G, u)
        u.visited = 1
        q.push(u);
        while(q.size())
                u = q.front()
                q.pop()
                for each v ∈ G.Adj[u]
                        if v.visited == false
                                    v.visited = u.visited + 1
                                    q.push(v)

 

 

예제 풀이

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int n, m, a[101][101], visited[101][101], y, x, sy, sx, ey, ex;

int main() {
  cin >> n >> m;
  cin >> sy >> sx;
  cin >> ey >> ex;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }

  queue<pair<int, int>> q;
  visited[sy][sx] = 1;
  q.push({sy, sx});
  while (q.size()) {
    tie(y, x) = q.front();
    q.pop();
    for (int i = 0; i < 4; i++) {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if (ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 0) {
        continue;
      }
      if (visited[ny][nx]) {
        continue;
      }
      visited[ny][nx] = visited[y][x] + 1;
      q.push({ny, nx});
    }
  }

  cout << visited[ey][ex] << "\n";

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << visited[i][j] << ' ';
    }
    cout << '\n';
  }
  return 0;
}

---

DFS vs BFS

• DFS
  • 메모리 덜 씀.
  • 절단점 등 구할 수 있음
  • 코드가 좀 더 짧으며 완탐의 경우에 많이 사용
• BFS
  • 메모리 더 씀.
  • 가중치가 같은 그래프내에서 최단거리 구할 수 있음
  • 코드가 더 김

---

트리 순회

• 트리 구조에서 각각의 구조를 정확히 한 번만, 체계적인 방법으로 방문하는 과정
  • 방문하는 순서에 따라 후위순회, 전위순회, 중위순회, 레벨순회가 존재.

후위순회

• Pseudo Code

postOrder(node)
        if (node.visited == false)
                postOrder(node->left)
                postOrder(node->right)
                node.visited = true

전위순회

• Pseudo Code (DFS)

preOrder(node)
        if (node.visited == false)
                node.visited = true
                preOrder(node->left)
                preOrder(node->right)

 

 

중위순회

• Pseudo Code

inOrder(node)
        if (node.visited == false)
                inOrder(node->left)
                node.visited = true
                inOrder(node->right)

 

 

레벨순회

• BFS

 

 

예제

#include <iostream>
#include <vector>

using namespace std;

vector<int> adj[1004];
int visited[1004];

void postOrder(int here) {
  if (visited[here] == 0) {
    if (adj[here].size() == 1)
      postOrder(adj[here][0]);
    if (adj[here].size() == 2) {
      postOrder(adj[here][0]);
      postOrder(adj[here][1]);
    }
    visited[here] = 1;
    cout << here << ' ';
  }
}

void preOrder(int here) {
  if (visited[here] == 0) {
    visited[here] = 1;
    cout << here << ' ';
    if (adj[here].size() == 1)
      preOrder(adj[here][0]);
    if (adj[here].size() == 2) {
      preOrder(adj[here][0]);
      preOrder(adj[here][1]);
    }
  }
}

void inOrder(int here) {
  if (visited[here] == 0) {
    if (adj[here].size() == 1) {
      inOrder(adj[here][0]);
      visited[here] = 1;
      cout << here << ' ';
    } else if (adj[here].size() == 2) {
      inOrder(adj[here][0]);
      visited[here] = 1;
      cout << here << ' ';
      inOrder(adj[here][1]);
    } else {
      visited[here] = 1;
      cout << here << ' ';
    }
  }
}

int main() {
  adj[1].push_back(2);
  adj[1].push_back(3);
  adj[2].push_back(4);
  adj[2].push_back(5);
  int root = 1;
  cout << "\n 트리순회: postOrder\n";
  postOrder(root);
  memset(visited, 0, sizeof(visited));

  cout << "\n 트리순회: preOrder\n";
  preOrder(root);
  memset(visited, 0, sizeof(visited));

  cout << "\n 트리순회: inOrder\n";
  inOrder(root);
  return 0;
}

---

정리