[알고리즘/문제풀이][BOJ 1260번] DFS와 BFS

DFS와 BFS는 DFS와 BFS에 대한 가장 기초적이면서도 중요한 문제입니다. DFS와 BFS에 대한 충실한 이해가 필요합니다. 

DFS의 경우 처음 발견된 노드를 기준으로 그 노드에 연결된 노드들을 탐색(DFS)를 하는 알고리즘입니다. 여기서 눈치챌 수 있듯이 DFS는 재귀함수로 구현할 수 있습니다.

BFS는 너비우선탐색이라는 이름에서 알 수 있듯이 루트 노드를 기준으로 방사형으로 탐색하는 알고리즘입니다. 즉, 루트 노드에서 거리가 1인 노드들을 전부 탐색한 다음 거리가 2인 노드를 탐색하는 방식으로 탐색이 진행됩니다. 이러한 방식으로 탐색하기 위해 BFS는 '큐'라는 자료구조를 활용하여 구현할 수 있습니다.

큐, DFS, BFS에 대한 설명은 다음과 같습니다.

2021.07.07 - [알고리즘/이론] - [알고리즘/이론]큐

[알고리즘/이론]큐

2021.07.03 - [알고리즘/이론] - [알고리즘/이론]깊이 우선 탐색(DFS)

[알고리즘/이론]깊이 우선 탐색(DFS)

2021.07.03 - [알고리즘/이론] - [알고리즘/이론]너비 우선 탐색(BFS)

[알고리즘/이론]너비 우선 탐색(BFS)

 

작성한 코드는 다음과 같습니다. 대부분의 BFS와 DFS 문제는 아래의 코드를 약간만 변경하여 해결할 수 있기 때문에 완벽하게 이해하지 못하더라도 암기하시길 권장드립니다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com/

int N, M, V;
int graph[1000 + 20][1000 + 20];
int temp1, temp2;
int DFS_visited[1000 + 20];
int BFS_visited[1000 + 20];

int queue[3000];
int rp, wp;

void BFS() {
	BFS_visited[V] = 1;
	queue[wp++] = V;
	printf("%d ", V);

	while (rp!=wp) {
		int temp = queue[rp++];
		for (int i = 1; i <= 1000; i++) {
			if (graph[temp][i] == 1) {
				if (BFS_visited[i] == 0) {
					BFS_visited[i] = 1;
					printf("%d ", i);
					queue[wp++] = i;
				}
			}
		}
	}
}

void DFS(int node) {
	
	
	for (int i = 1; i <= 1000; i++) {
		if (graph[node][i] == 1) {
			if (DFS_visited[i] == 0) {
				DFS_visited[i] = 1;
				printf("%d ", i);
				DFS(i);
			}
		}
		
	}
}

int main(void) {
	scanf("%d %d %d", &N, &M, &V);

	for (int i = 0; i < M; i++) {
		scanf("%d %d", &temp1, &temp2);
		graph[temp1][temp2] = 1;
		graph[temp2][temp1] = 1;
	}

	DFS_visited[V] = 1;
	printf("%d ", V);
	DFS(V);
	printf("\n");
	BFS();

	return 0;
}

문제의 지문은 다음 링크에서 확인하실 수 있습니다.

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