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

 

 

<DFS & BFS>

#include <iostream>
#include <stdio.h>
#include <queue>
#include <memory.h>
#include <algorithm>
using namespace std;

int arr[1001][1001];
int visit[1001];
int N, M, V;
int u, v;

void dfs(int x) // 재귀 dfs
{
	int i = 0;

	visit[x] = 1; // 방문 표시
	printf("%d ", x); // 방문한 점 출력

	for (i = 1; i <= N; i++)
		if (arr[x][i] == 1 && visit[i] == 0)
		{
			
			dfs(i);
		}
	if (i == N) return; // i가 N개의 모든 점을 검사했다면 반환
}

void bfs(int x)
{
	queue<int> q; // 큐 생성
	int i = 0;

	q.push(x); // 시작점 큐에 삽입

	while (!q.empty()) // 큐에 원소가 하나도 없을 시 탈출
	{
		int next_x = q.front(); // 큐 맨앞의 원소를 다음 탐색할 점으로 지정
		visit[next_x] = 1; // 방문 표시
		printf("%d ", next_x); // 방문 한 점 출력
		q.pop(); // 큐 맨 앞 데이터 삭제

		for (i = 1; i <= N; i++)
			if (arr[next_x][i] == 1 && visit[i] == 0)
			{
				//next_x점과 i점이 연결되어있고 i점은 방문기록이 없다면
				q.push(i); // 큐에 i점 삽입
				visit[i] = 1; // i점은 미리 방문표시(미리 하지 않으면 중복으로 방문할 수도 있음)
			}
	}
}

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

	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &u, &v);
		// arr = 각 점의 연결 정보를 알려주는 행렬
		arr[u][v] = 1;
		arr[v][u] = 1;
	}

	dfs(V);

	printf("\n");
	memset(visit, 0, sizeof(visit)); // 방문기록 초기화

	bfs(V);



}

DFS와 BFS의 가장 기초적인 문제.

DFS와 BFS는 이론적으로 이해가 가지만 막상 코드로 구현을 하려고 하면 잘 떠오르지 않고 감을 못 잡았었는데 이 무제를 풀면서 DFS(Depth First Search, 깊이 우선 탐색) BFS(Breath First Search, 너비 우선 탐색)의 감을 잡는데 도움이 되었다. 

DFS의 경우 재귀적으로 구현을 하고 BFS는 큐를 통해 구현을 하였다. 문제풀이에 가장 중요한 것은 각 노드의 방문 기록을 저장하는 배열의 존재이고 각 노드의 연결 정보를 나타낸 NxN크기의 2차원 배열이다.

위 사진은 예제입력1이고 간선의 정보가 위와 같다면 arr배열은

arr[  ][  ]	0	1	2	3	4
0	0	0	0	0	0
1	0	0	1	1	1
2	0	1	0	0	1
3	0	1	0	0	1
4	0	1	1	1	0

 위와 같은 표로 형성이 된다.

 

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

1260번: DFS와 BFS