백준 1260 DFS와 BFS 인접 리스트로 풀이(BFS/DFS)

문제

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

다시 푸는 이유

컴퓨터가 이해할 수 있는 그래프 표현은 인접 행렬이나 인접 리스트를 사용한다. 이전 문제 풀이에서는 인접 행렬을 사용했기 때문에 이번에는 인접 리스트를 사용해서 그래프를 표현할 것이다.

그래프 표현

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

vector<int> map[1001]; // 인접 리스트로 그래프 표현
int visited[1001]; // 현재 방문한 정점

// ~~중략~~ 

// 간선 연결
for (int i = 0; i < M; i++) {

		cin >> v1 >> v2;

		map[v1].push_back(v2);
		map[v2].push_back(v1);
}

DFS

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

	// 현재 노드에 연결되었고 방문하지 않은 노드를 재귀호출
	for (int i = 0; i < map[v].size(); i++) {
		int x = map[v][i]; // 연결 정점
		if (visited[x] == 0)
			DFS(x);
	}
}

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 = 0; i < map[next].size(); i++) {
			int x = map[next][i]; // 연결 정점
			if (visited[x] == 0) {
				q.push(x); // 다음 방문할 노드 삽입
				visited[x] = 1; // 중복 노드 삽입 방지를 위해 미리 기록
			}

		}
	}
}

전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> map[1001]; // 인접 리스트로 그래프 표현
int N; // 노드의 개수
int M; // 간선의 개수
int V;  // 탐색을 시작할 정점의 번호
int visited[1001]; // 현재 방문한 정점

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

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

	// 현재 노드에 연결되었고 방문하지 않은 노드를 재귀호출
	for (int i = 0; i < map[v].size(); i++) {
		int x = map[v][i]; // 연결 정점
		if (visited[x] == 0)
			DFS(x);
	}
}

// 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 = 0; i < map[next].size(); i++) {
			int x = map[next][i]; // 연결 정점
			if (visited[x] == 0) {
				q.push(x); // 다음 방문할 노드 삽입
				visited[x] = 1; // 중복 노드 삽입 방지를 위해 미리 기록
			}

		}
	}
}

int main() {

	// 노드의 개수, 간선의 개수, 시작 정점 입력
	cin >> N >> M >> V;

	int v1, v2; // 연결할 노드

	// 간선 연결
	for (int i = 0; i < M; i++) {

		cin >> v1 >> v2;

		map[v1].push_back(v2);
		map[v2].push_back(v1);
	}

	// 정점 번호가 작은 것을 먼저 방문하게 하기 위한 작업
	for (int i = 1; i <= N; i++)
		sort(map[i].begin(), map[i].end());

	//DFS 수행
	DFS(V);

	// rest 수행
	reset();
	cout << "\n";

	//BFS 수행
	BFS(V);

	return 0;
}

참조

• C로 배우는 쉬운 자료구조 4탄, 이지영, 한빛아카데미, 2022
• 4차 산업혁명 시대의 이산수학, 김대수, 생능출판, 2019
• 백준 1260 DFS와 BFS C++ [컴공과고씨]
• [자료구조] C++ vector로 그래프 구현하기 (포인터 없이 인접리스트 구현)