[BOJ] 백준 1260 DFS와 BFS

[BOJ] 백준 1260 DFS와 BFS

문제 링크 : https://www.acmicpc.net/problem/1260

학교 알고리즘 동아리에서 그래프 수업을 나가는데, 거기서 추천해준 첫번째 문제 입니다.

자료구조 수업까지 나가고 있는데, 거기서 배우게 되는 내용이라 더 집중하였습니다.

하지만 매우 생소하였습니다.

DFS와 BFS를 이용한 미로찾기는 이제 잘 할 자신이 있는데,(배추지렁이 문제까지 풀었기에) 하지만 그래프 문제는 약간 달랐습니다.

그래프 문제는 인접리스트와 인접행렬로 나누어 집니다. 각각 문제는 유/불리가 있습니다.

- 인접행렬이 유리한 경우 :

1. N*M 크기의 그래프가 주어진 경우

2. 정점 번호가 순서 없이 주어졌지만, 결과는 정렬된 형태의 그래프에 기반했을때.

3. 해당 칸을 방문했는지 여부 판단 쉬움.

- 인접 리스트가 유리한 경우

1. 입력에 N*M 행렬이 주어지지 않고, 정점과 정점 연결 정보만 알려주었을 경우

2. 메모리 아껴야 하는 경우

3. 연결관계만 알수 있어서 컴팩트함.

DFS는 스택을 이용한다고 알고 있습니다. stack은 재귀함수(recursion)도 이용하고 있습니다. 따라서 앞으로는 재귀함수로 DFS를 대처한다고 생각하면 됩니다.

BFS는 큐를 이용합니다. 한 정점에서 연결된 모든 점을 큐에 넣고 하나씩 빼면서 다음 성분과 연결된 점들을 탐색합니다.

소스코드:

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAX = 1000 + 1;

int N, M, V;
vector graph[MAX];
bool visited[MAX];


void DFS(int idx) {
 cout << idx << ' ';
 for (int i = 0; i < graph[idx].size(); i++) {
  int connected = graph[idx][i];
  if (!visited[connected]) {
   visited[connected] = true;
   DFS(connected);
  }
 }
}
void BFS(int idx) {
 queue q;
 q.push(idx);
 visited[idx] = true;
 while (!q.empty()) {
  int cur = q.front();
  q.pop();
  cout << cur << ' ';
  for (int i = 0; i < graph[cur].size(); i++) {
   int next = graph[cur][i];
   if (!visited[next]) {
    visited[next] = true;
    q.push(next);
   }
  }
 }
}
int main() {
 cin >> N >> M >> V;
 for (int i = 0; i < M; i++) {
  int from, to;
  cin >> from >> to;
  graph[from].push_back(to);
  graph[to].push_back(from);
 }
 for (int i = 1; i < N; i++) {
  sort(graph[i].begin(), graph[i].end());
 }
 visited[V] = true;
 DFS(V);
 cout << endl;
 memset(visited, false, sizeof(visited));
 BFS(V);
}