[C / C++] 백준 1260번 - DFS 와 BFS

백준 1152번 : https://www.acmicpc.net/problem/1260

1152번: 단어의 개수

✅ 문제 설명

이 문제는 DFS BFS를 다루는 문제로

정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V를 입력하고,

양방향 간선이라는 가정 하에 첫째줄에 DFS, 둘째줄에 BFS를 수행한 결과를 출력하는 문제이다.

---

✅ 알고리즘 설명

간단하게 생각하면,

DFS(깊이우선탐색)는 스택, BFS(너비우선탐색)는 큐로 구현한다고 볼 수 있다.

 

DFS는 정점 V를 시작으로 그 정점과 연결된 정점들을 모두 찾은 후,

더 이상 연결된 것이 없으면 빠져나와 다음 정점을 탐색해야 한다.

 

그에 반해 BFS는 정점 V와 직접적으로 연결된 같은 레벨의 모든 정점들을 탐색하고,

그 다음 레벨의 정점들을 모두 탐색하는 순서로 진행된다.

 

DFS는 정점 V를 시작으로 연결된 정점들을 차례로 스택에 push하고,

탐색할 때마다 스택에서 pop하는 형식으로 진행하면 된다.

 

BFS는 정점 V와 연결된 같은 레벨의 정점들을 차례로 큐에 push하고,

앞에서부터 차례로 pop하는 형식으로 진행하면 된다.

---

⚡ [ DFS (깊이우선탐색) ]

 

1. 정점 V로 들어감

 

2. 정점 V에서 제일 작은 수 A로 들어감

-1) A에서 제일 작은 수 A-1로 들어감

-2) A-2, A-3, A-4 ... 쭉쭉 들어가서 더이상 연결된 노드가 없으면 나옴

-3) A-4에서 나왔다고 가정하면 A-3과 연결된 노드를 찾아감

-4) A-3을 나오면 A-2와 연결된 노드를, A-2를 나오면 A-1과 연결된 노드를 쭉쭉 찾아감

 

3. 결국 A를 다 탐색하면 정점 V와 연결되며, A다음으로 작은 수 B 탐색

 

4. 모든 간선을 탐색할 때까지 2번 탐색 반복

---

⚡ [ BFS (너비우선탐색) ]

 

1. 정점 V로 들어감

 

2. 정점 V와 직접적으로 연결된 A,B,C....를 작은 수부터 탐색

-1) 그 다음으로 A,B,C...와 직접적으로 연결된 A-1, B-1, C-1을 차례로 탐색

-2) A-2, B-2, C-2... -> A-3, B-3, C-3... 이런식으로 계속해서 같은 레벨의 정점들을 탐색

 

3. 모든 간선을 탐색할 때까지 2번 탐색 반복

---

✅ 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

// n - 정점의 개수
// m - 간선의 개수
// v - 정점의 번호
int n, m, v;
int arr[1000][1000] = { 0 }; // 양방향 간선 (a,b), (b,a) 모두 저장할 수 있도록 2차원 배열
int idx_BFS[1000] = { 0 }; // BFS 탐색 여부 확인용
int visit_DFS[1000] = { 0 }; // DFS 탐색 여부 확인용

void start_DFS(int now) {
	printf("%d ", now); // 탐색한 정점 출력
	/* 정점 now 탐색했다고 표시 */
	visit_DFS[now - 1] = 1; // index는 0부터기 때문에 now-1

	/* 탐색한 애를 기준으로 제일 작은 수 탐색 시작 */
	for (int i = 0; i < n; i++) {
		/* 무언가 값이 있고 탐색한 적 없다면 */
		if ((arr[now - 1][i] == 1) && (visit_DFS[i]) == 0)
			start_DFS(i + 1); // 걔를 탐색하도록 재귀 함수로 보내줌
	}
	return;
}

void start_BFS() {
	static int cnt = 0;// 탐색한 정점의 개수
	static int idx = 0;// 탐색할 정점의 index
	
	int now = v; // 탐색할 정점 저장
	int *next = (int*)calloc(n, sizeof(int)); // 다음 탐색할 정점 저장

	printf("\n%d", now); // 시작 정점 출력
	/* 모든 정점 탐색하면 탈출 */
	while (cnt < n - 1) {
		for (int i = 0; i < n; i++) { // 같은 레벨 탐색
			/* 해당 정점과 직접 연결된 값이 있다면 */
			if (arr[now - 1][i] == 1 && idx_BFS[i] == 1) {
				printf(" %d", i + 1); // 같은 레벨들 출력
				idx_BFS[i] = 0; // 다시 탐색 못하게 0으로 바꿈
				next[cnt] = i + 1; // 같은 레벨들 저장
				cnt++; // 인덱스 ++
			}
		}

		/*
		처음 정점이랑 연결된 간선 없으면 바로 break
		간선 하나여도 break
		*/
		if ((now == v && cnt == 0) || (now == v && cnt == 1))
			break;
		else {
			// 이제 같은 레벨 다 탐색함
			idx_BFS[now - 1] = 0; // 이 레벨은 이제 탐색함
			now = next[idx]; // 다음 수를 탐색할 정점으로 저장
			idx++; // 위와 같은 레벨에서 그 다음으로 작은 정점
		}
	}
	free(next);
	return;
}

int main(void) {
	scanf("%d%d%d", &n, &m, &v);

	/* 간선의 숫자만큼 반복문 */
	int a, b; // 간선이 연결하는 두 정점의 번호
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);

		/* 양방향 간선이므로 둘 다 저장 */
		arr[a - 1][b - 1] = 1; // (a,b)를 연결하는 간선 있다고 바꾸기
		arr[b - 1][a - 1] = 1; // (b,a)를 연결하는 간선 있다고 바꾸기

		/* 일단 이 인덱스에는 최소 1개 이상의 값이 있음 */
		idx_BFS[a - 1] = 1, idx_BFS[b - 1] = 1;
	}

	if (m == 0) // 간선이 0개이면
		printf("%d\n%d", v, v);
	else {
		start_DFS(v); // 깊이 우선 탐색
		start_BFS();  // 너비 우선 탐색
	}
	return 0;
}

 

ex) N = 4

idx	0	1	2	3
0	0	1	0	0
1	1	0	0	0
2	0	0	0	0
3	0	0	0	0

a=1, b=2라고 가정했을 때 (a,b) (b,a) 모두 저장하여

1을 먼저 탐색하면 2로 연결,

2를 먼저 탐색하면 1로 연결하여 양방향으로 탐색할 수 있도록 만듦

---

https://github.com/2hyunjinn/Baekjoon/blob/main/Baekjoon_1260.cpp

GitHub - 2hyunjinn/Baekjoon