백준 #1260 DFS와 BFS (c++)

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

드.디.어. 등장했다 !!

아주그냥 dfs와 bfs를 진짜 제대로 물어보겠다는 문제

 

이전 글에서 간략하게 다뤘던 dfs와 bfs를 사용해보면 되겠다.

(이전 글 링크)

https://hamma-cediary.tistory.com/4

백준 #1012 유기농 배추 (c++)

하지만 dfs와 bfs를 사용하기 전에 그래프에 대한 최소한의 지식은 있어야 이 문제를 풀 수 있을 것이기 때문에

정말 간략하게만 설명하고자 한다.

---

그래프를 생각하면 흔히들 중고등학교 때 배웠던 xy좌표 위의 2차함수 3차함수 등등을 생각하는데,

여기서 말하는 그래프는 그 그래프가 아니라 노드와 간선으로 이루어진 자료구조 형태를 말한다.

그래프 예시

위의 그래프 G에서 노드는 a b c d e f g h 이고, 간선은 각 노드들을 연결하는 모든 선을 의미한다.

 

이러한 그래프를 우리가 알고리즘 문제를 풀 때에는 두 가지의 형태로 표현할 수 있는데,

 

첫번째가 바로 adjacency matrix, 즉 인접 행렬이다.

그래프 G의 인접 행렬

각각 가로와 세로축에는 모든 노드들을 두고, 가로와 세로값이 만나는 지점에는 두 노드가 만나면 1, 만나지 않으면 0으로 표시한다.

cf) 두 노드 사이에 간선이 2개 이상 존재할 때에는 간선의 수로 표현하기도 한다.

 

예를 들어, 위의 그래프 그림에서 노드 g와 h가 만나므로 g와 h가 만나는 곳에는 1로 표시되어 있다.

 

여기서 가로와 세로축이 모두 노드값으로 설정되어 있기 때문에 인접 행렬은 대각선을 기준으로 대칭을 이루게 된다. (Aij = Aji)

 

 

그래프를 표현하는 두번쨰 방법은 adjacency list, 즉 인접 리스트이다.

그래프 G의 인접 리스트

각 노드들을 하나의 배열에 배치시키고, 각 노드마다 간선으로 연결된 노드들이 있으면 그 노드들을 그 노드의 배열값에서 연결리스트의 형태로 추가해준다. (c++에서는 벡터를 사용하여 표현할 것이다)

 

앞에서 언급했던 예시인 노드 g와 h는 간선으로 연결되어 있으므로 각각 노드 g와 h에는 서로의 값이 연결리스트에 존재한다.

 

---

이제 그래프의 정의와 표현방법도 알았으니, 이 문제를 푸는건 어렵지 않을 것이다.

+ 그래프의 두가지 표현방법 중 인접 리스트를 사용할 것이다.

 

간선이 양방향으로 주어졌다고 하니, 간선으로 연결된 두 정점들의 값을 입력받을 때 앞의 노드 g와 h처럼 서로의 값을 넣어줄것이다.

 

v[a].push_back(b);

v[b].push_back(a);

 

그렇게 만들어진 그래프를 각각 dfs와 bfs로 모든 노드들을 탐색할 것인데,

 

dfs는 이전 글인 "유기농 배추"에서도 볼 수 있듯이 재귀함수의 형태로 시작 노드에서 출발하여 연결된 노드들을 쭈욱 파고 들어가는 형식으로 모든 노드들을 한번씩 탐색할 것이다.

 

+ 이미 탐색한 노드는 bool visited[1010]에서 그 노드값에 해당하는 원소를 true로 바꿔줄 것이다.

 

bfs는 이전 글에서도 언급했듯이 노드들을 두루두루 훑어보는 과정이므로

현재의 노드에서 연결된 노드들을 모두 탐색한 다음에 그 노드들과 연결된 또다른 노드들을 탐색해야한다.

이러한 과정을 수행할 때 우리는 큐(queue)라는 자료구조를 사용할 수 있다.

+ 스택이 아닌 큐를 사용하는 이유는 push한 순서대로 노드를 탐색하기 위해서다 (FIFO, First in First Out)

 

이후에 탐색할 노드들을 큐에 push해놓고 (visited값도 true로 바꿔준다)

큐를 pop하여 나온 노드로 넘어가서 연결된 또다른 노드들을 큐에 push하는 형태로 진행하면 되는데,

앞의 dfs에서도 그러했듯이 중복 탐색을 피하기 위해서 큐에 노드값을 push하기 전에 이미 탐색했는지 여부를 visited의 원소값을 통해 확인하는 과정을 거치는 것을 잊지 말아야 한다.

 

그 과정을 큐가 비워지기 전까지 진행하면 된다.

 

while(!q.empty())

 

마지막으로 문제에서도 언급되었듯이, 연결된 노드가 여러개일 경우 가장 작은 원소값부터 탐색한다고 했기 때문에

그래프의 간선들을 모두 입력받은 뒤에 각 노드별로 벡터를 정렬해주는 것을 잊지 말자.

난 까먹고 그냥 제출해서 이미 한번 틀려버렸다..

 

(제출한 코드)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;

int N, M, V;
vector<int> v[1010];
bool visited[1010];

void dfs(int curr) {
  cout << curr << " ";
  visited[curr] = true;
  if(!v[curr].empty())
    for(auto i : v[curr])
      if(!visited[i])
        dfs(i);
}

void bfs(int start) {
  queue<int> q;
  q.push(start);
  visited[start] = true;
  while(!q.empty()) {
    int curr = q.front();
    cout << curr << " ";
    q.pop();
    for(auto i : v[curr])
      if(!visited[i]) {
        visited[i] = true;
        q.push(i);
      }
  }
}

int main() {
  FASTIO;
  cin >> N >> M >> V;
  for(int i=0; i<M; i++) {
    int a, b; cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for(int i=1; i<=N; i++) sort(v[i].begin(), v[i].end());
  dfs(V);
  cout << '\n';
  for(int i=0; i<1010; i++) visited[i] = false;
  bfs(V);
}

---

이렇게 벌써 dfs bfs 문제를 두개나 풀었는데, 그 과정에서 단순히 이론으로만 듣는 것 그 이상으로

두 탐색 알고리즘을 나의 것으로 만들 수 있었던 것 같다.

 

이번주까지는 Class3에 있는 다른 dfs bfs 문제들도 더 풀어볼 예정이다.

 

dfs bfs 를 완전히 마스터하는 그날까지 화이팅 !!