[백준] DFS와 BFS

백준 1260번 문제

 

이 문제는 가장 기본적인 DFS / BFS 문제로 기본 개념만 알고있다면 쉽게 풀 수 있다. 성공한 코드를 먼저 확인해보자.

 

#include <stdio.h>
#define MAX 1001

int metrix[MAX][MAX];
int visited[MAX * MAX];

void DFS (int v, int N) {
	// 정점 출력
	printf("%d ", v);
	
	// 방문 표시
	visited[v] = 1;
	
	// 인접 정점 체크
	for (int d = 1; d <= N; d++) {
		// 방문하지 않았고 이동 가능하다면
		if (!visited[d] && metrix[v][d]) {
			DFS(d, N);
		}
	}
}

void BFS (int v, int N) {
	// 큐에 관련된 변수 선언
	int front = -1, rear = -1;
	int queue[MAX * MAX] = { 0 };
	
	// 첫번째 추가
	rear++;
	queue[rear] = v;
	
	// 방문 표시
	visited[v] = 1;
	
	// 일단 출력
	printf("%d ", v);
	
	// 너비 우선 탐색
	while (front < rear) {
		// 큐에서 꺼내기
		front++;
		int nextV = queue[front];
		
		// 인접 정점 체크
		for (int d = 1; d <= N; d++) {
			// 방문하지 않았고, 이동이 가능하다면
			if (!visited[d] && metrix[nextV][d]) {
				rear++;
				visited[d] = 1;
				queue[rear] = d;
				
				printf("%d ", d);
			}
		}
	}
}

void init (int N) {
	printf("\n");
	for (int i = 1; i <= N; i++) {
		visited[i] = 0;
	}
}

int main(void) {
	int N = 0;
	int M = 0;
	int V = 0;
	
	scanf("%d %d %d", &N, &M, &V);
	
	for (int i = 0; i < M; i++) {
		int s = 0;
		int d = 0;
		
		scanf("%d %d", &s, &d);
		
		metrix[s][d] = 1;
		metrix[d][s] = 1;
	}
	
	DFS(V, N);
	
	init(N);
	
	BFS(V, N);
	
	return 0;
}

 

위 문제를 풀면서 반드시 필요한 개념 몇가지에 대해서 알아보자.

 

 

큐

 

너비 우선 탐색 (BFS) 의 경우에는 대상 정점과 인접한 모든 정점을 한번의 싸이클에서 모두 방문하기 때문에 인접 정점을 저장할 수 있는 자료구조가 필요하다. 이 때, 큐를 사용하여 인접 정점을 차례대로 방문한다. C언어에서는 큐에 대한 라이브러리가 기본으로 제공되지 않기 때문에, front 변수와 rear 변수를 통해 간단하게 구현하였다. C언어의 경우 우선순위 큐도 직접 구현해야 하는데, 조간만 알아보자. 이런 문제가 나오면 C언어에서는 시간이 상당히 많이 소요된다.

 

참고로 깊이 우선 탐색 (DFS) 의 경우에는 대상 정점과 인접한 정점 하나를 방문하고, 방향을 선택 후 방문한 정점과 인접한 또다른 정점을 방문하는 등 하나만 파고들며 방문한다. 더이상 방문한 정점이 없다면, 이전 갈림길이 있던 정점으로 돌아가야 하므로 스택이나 재귀 호출을 사용하여 구현한다.

 

 

인접 행렬

 

그래프를 컴퓨터 상에서 표현할 때 사용하는 방법 중 가장 쉬운 방법으로 2차원 배열을 통하여 정점 관계를 표시한다. 정점의 갯수가 많을경우 메모리를 크게 점유하는 문제가 있으나, 인덱스로 접근하기 때문에 찾는 속도가 빠르고 구현하기 쉽다는 장점이 있어 그래프 알고리즘 문제에서는 대부분 인접 행렬을 사용하여 관계를 나타낸다.

 

양방향 그래프의 인접행렬

인접 행렬을 사용할 때 주의사항이 있는데, 그래프의 방향성에 따라 인접 행렬의 형태가 달라진다. 위의 그림은 양방향 그래프에 대한 인접행렬을 나타낸 그림이다. 양방향 인접 행렬의 경우 metrix[startV][destV] == metrix[destV][startV] (시작 정점 -> 도착 정점 == 도착 정점 -> 시작 정점) 가 성립되므로 인접 행렬에서 값이 대칭 형태를 나타낸다.

 

그러나 단방향 그래프의 경우에는 metrix[startV][destV] /= metrix[destV][startV] (시작 정점 -> 도착 정점 /= 도착 정점 -> 시작 정점) 이 성립되지 않으므로 대칭형태를 띄지 않는다. 이 경우에는 인접 행렬에서 값이 참일때만 정점간 이동을 수행한다.