백준 1260 DFS와 BFS (BFS/DFS)

문제

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

문제내용

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력1

1 2 4 3
1 2 3 4

문제풀이

문제헤설

그래프를 표현하고, DFS와 BFS를 사용해서 탐색하는 문제.

생각한 것

• 그래프 표현 방법
• DFS 방법
• BFS 방법

그래프 표현

그래프는 그림을 이용하여 표현하는 것으로 가장 자연스럽고 이해하기에 가장 쉬운 방법이다. 그러나 컴퓨터는 그림으로 표현된 정보를 이용할 수 없기 때문에 인접 행렬이나 인접 리스트에 의해 표현된다. 그래서 그래프를 표현할 방법으로 인접 행렬를 사용할 것이고 2차원 배열로 인접 행렬을 표현할 것이다.

• 원래 정점의 개수가 N이면 N X N 행렬로 표현한다.
• 여기서 고려할 점은 배열 크기가 N이면 인덱스는 0 ~ N-1로 표현된다.
• 하지만 문제에서 “정점 번호는 1번부터 N번까지”라고 명시했기 때문에 인덱스 0을 제외하고 1부터 N까지 표현하기 위해서 배열 크기를 N+1로 한다.
• 그리고 문제에서 “정점의 개수 N(1 ≤ N ≤ 1,000)”이기 때문에 배열 크기는 1001 이다.

int map[1001][1001]; // 그래프 표현
int visited[1001]; // 현재 방문한 정점 체크

// ~~중략~~ 

// 간선 연결
for (int i = 0; i < M; i++) {
	cin >> a >> b;
	map[a][b] = 1;
	map[b][a] = 1;
}

DFS

1. 현재 방문한 노드를 기록한다.
2. 1번부터 N번까지 노드를 탐색한다.
3. 현재 노드와 연결되었고 방문하지 않은 노드가 있으면 그 노드로 재귀호출

void DFS(int v) {
	visited[v] = 1; // 방문기록
	cout << v << " "; // 방문한 노드 출력

	// 그래프 탐색 방법
	for (int i = 1; i <= N; i++) {
		// 현재 정점과 연결되어있고 방문되지 않았으면 발동
		if (map[v][i] == 1 && visited[i] == 0)
			DFS(i);
	}
}

BFS

1. 시작 노드를 큐에 넣는다.
2. 큐가 비었는지 검사한다.
3. 큐 맨 앞에 노드를 방문한다.
4. 현재 방문한 노드를 기록한다.
5. 기록된 노드는 큐에서 제거한다.
6. 1번부터 N번까지 노드를 탐색한다.
7. 현재 노드와 연결되었고 방문하지 않은 노드가 있으면 그 노드를 큐에 집어 넣고 방문 기록한다. (중복으로 큐에 삽입되는 것을 방지)

void BFS(int v) {
	queue<int> q; // BFS용 큐 생성
	q.push(V); // 시작노드 큐에 넣음

	while (!q.empty()) {
		int next = q.front(); // 큐 맨 앞에 값을 방문
		visited[next] = 1; // 방문기록
		cout << next << " "; // 방문한 노드 출력
		q.pop(); // 큐에서 제거

		for (int i = 1; i <= N; i++) {
			if (map[next][i] == 1 && visited[i] == 0){
				q.push(i); // 큐에 넣음
				visited[i] = 1; // 미리 방문기록해서 중복 방지
			}
		}
	}
}

전체코드

#include <iostream>
#include <queue>

using namespace std;

int map[1001][1001]; // 그래프 표현
int N; // 정점의 개수
int M; // 간선의 개수
int V;  // 탐색을 시작할 정점의 번호
int visited[1001]; // 현재 방문한 정점 체크

// 방문 초기화
void rest() {
	for (int i = 1; i <= N; i++)
		visited[i] = 0;
}

// DFS 함수
void DFS(int v) {
	visited[v] = 1; // 방문기록
	cout << v << " "; // 방문한 노드 출력

	// 그래프 탐색 방법
	for (int i = 1; i <= N; i++) {
		// 현재 정점과 연결되어있고 방문되지 않았으면 발동
		if (map[v][i] == 1 && visited[i] == 0)
			DFS(i);
	}
}

// BFS 함수
void BFS(int v) {
	queue<int> q; // BFS용 큐 생성
	q.push(V); // 시작노드 큐에 넣음

	while (!q.empty()) {
		int next = q.front(); // 큐 맨 앞에 값을 방문
		visited[next] = 1; // 방문기록
		cout << next << " "; // 방문한 노드 출력
		q.pop(); // 큐에서 제거

		for (int i = 1; i <= N; i++) {
			if (map[next][i] == 1 && visited[i] == 0){
				q.push(i); // 큐에 넣음
				visited[i] = 1; // 미리 방문기록해서 중복 방지
			}
		}
	}
}

int main() {
	int a, b; // 간선 연결할 정점
	
	// 데이터 입력
	cin >> N >> M >> V;
	
	// 간선 연결
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;
	}

	// DFS 수행
	DFS(V);

	// 정점 초기화 수행
	rest();
	cout << "\n";

	// BFS 수행
	BFS(V);

}

참조

• C로 배우는 쉬운 자료구조 4탄, 이지영, 한빛아카데미, 2022
• 4차 산업혁명 시대의 이산수학, 김대수, 생능출판, 2019
• [백준] 1260 DFS와 BFS C++ (BFS/DFS)
• [백준][Python] 1260번 DFS와 BFS(DFS/BFS 기본 구현 자세히)