BOJ 1260 DFS와 BFS

📎Problem Link

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

1260번: DFS와 BFS

📋 문제 정리

• 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것부터 방문
• 더 이상 방문할 수 없는 경우 종료
• 정점 번호는 1번부터 N번까지!
• 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색 시작 정점 번호 V
• 다음 줄부터 M개의 줄에는 간선이 연결하는 두 정점 번호 입력
• 이 때 간선은 양방향

 

📌 예제 1

• DFS 실행 시
  (1) 1에서 제일 숫자가 적은 2로 이동
  (2) 2에서 숫자가 제일 적은 것은 1이지만 이미 방문했기 때문에 4로 이동
  (3) 4에서 숫자가 제일 적은 것은 1이지만 이미 방문했기 때문에 3으로 이동
  (4) 3과 연결된 모든 노드는 이미 방문했기 때문에 DFS 종료
  
  
• BFS 실행 시
  (1) 1에서 제일 숫자가 적은 2로 이동
  (2) Breadth First Search이므로 1에서 2다음인 3으로 이동
  (3) Breadth First Search이므로 1에서 2, 3다음인 4로 이동
  (4) 모든 노드를 방문했기 때문에 BFS 종료

 

📌 예제 2

 

• DFS 실행 시
  (1) 3에서 숫자가 제일 적은 것이 1이기 때문에 1로 이동
  (2) 1에서 숫자가 제일 적은 것이 2이기 때문에 2로 이동
  (3) 2에서 숫자가 제일 적은 것은 1이지만 이미 방문했기 때문에 5로 이동
  (4) 5에서 숫자가 제일 적은 것은 2이지만 이미 방문했기 때문에 4로 이동
  (5) 4에서 갈 수 있는 모든 노드는 이미 방문했기 때문에 DFS 종료
  
  
• BFS 실행 시
  (1) 3에서 갈 수 있는 모든 노드를 먼저 방문하는데 이 중 제일 숫자가 적은 것은 1이기 때문에 1에 방문 (이때 queue에 2 들어감)
  (2) 3에서 갈 수 있는 노드들 중 1은 방문했기 때문에 4로 이동 (이 때, queue에 5 들어감)
  (3) queue의 맨 앞에 있는 2 방문
  (4) queue의 맨 앞에 있는 5 방문
  (5) 모든 노드를 방문했으므로 BFS 종료

 

 

📌 예제 3

 

• DFS 실행 시
  (1) 1000에서 갈 수 있는 유잏한 노드 999로 이동
  (2) 모든 노드 방문했기 때문에 DFS 종료
  
  
• BFS 실행 시
  (1) 1000에서 갈 수 있는 유잏한 노드 999로 이동
  (2) 모든 노드 방문했기 때문에 BFS 종료

---

💻 Code

 

int main() {
	int StartPoint;
	Graph algo;
	cin >> algo.Node >> algo.Edge >> StartPoint;

	for (int i = 0; i < algo.Edge; i++) {
		int Node1, Node2;
		cin >> Node1 >> Node2;
		algo.v[Node1].push_back(Node2);
		algo.v[Node2].push_back(Node1);
	}

	for (int i = 1; i <= algo.Node; i++) //작은 node부터 가야하기 때문에 사전에 오름차순 정렬해주기
		sort(algo.v[i].begin(), algo.v[i].end());

	algo.DFS(StartPoint);
	cout << endl;
	memset(algo.visited, false, sizeof(algo.visited));
	algo.BFS(StartPoint);
}

이번에는 main문부터 보려고 한다. 1번 예시로 코드를 살펴보도록 하자.

양방향 노드이기 때문에 연결된 노드를 양쪽에 모두 넣어줬다. 예를 들어서 5,4가 입력되면 v[4]에 5를, v[5]에 4를 넣었다. 이렇게 하면 vector v는 다음과 같이 구성된다.

내 코드에서 유의해야 할 점은 v[0]은 비어있다는 점이다. 이 부분을 간과하고 간다면 메모리 접근 오류가 발생할 것이다.

위의 경우는 이미 오름차순으로 정렬돼있지만 그렇지 않은 경우도 있을 수 있기 때문에 sort 함수를 작성했다.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring> //백준에서 memset에서 사용하려면 필요
using namespace std;


class Graph {
public:
	int Node, Edge;
	vector<int> v[1001];
	queue<int> q;
	bool visited[1001] = { false };

	void DFS(int sp){
		while (visited[sp] != 1) {
			visited[sp] = true;
			cout << sp << " ";
			for (int i = 0; i < v[sp].size(); i++) {
				DFS(v[sp][i]);
			}
		}
	}

	void BFS(int sp) {
		visited[sp] = 1;
		q.push(sp);

		while (!q.empty()) {
			int currentnum = q.front();
			q.pop();
			cout << currentnum << " ";
			for (int i = 0; i < v[currentnum].size(); i++) {
				int index = v[currentnum][i];
				if (visited[index] != 1) {
					q.push(index);
					visited[index] = 1;
				}
			}
		}
	}
};

DFS 함수부터 살펴보자. DFS 함수는 아주 단순하다. 방문한 적이 없는 노드에 한해서만 while문 안의 코드를 실행시키도록 했다.

 

BFS 함수는 다음과 같다. BFS의 특징은 Queue를 사용했다는 것이다. BFS 함수의 맨 위 두줄은 BFS가 처음 실행됐을 때만 돌아간다.

while문안으로 들어가게 되면, 먼저 현재 node와 연결된 다른 노드들에 대한 방문 여부를 확인한다. 이렇게 코드를 작성하면 똑같은 노드를 queue에 반복적으로 넣는 것을 방지할 수 있다. 암튼 위와 같이 작성하고 실행시키면 현재 노드인 currentnum과 연결된 모든 노드들을 다 훑고 종료할 수 있다.

---

이번에는 1년 전에 비해 메모리나 속도면에서 아주 크게 줄었다! 심지어 코드 길이도 줄었는데 말이다. 이번 코드는 당당하게 더 효율적으로 짰다고 말할 수 있어서 기분이 좋다><