[백준/C++] 1260 DFS와 BFS (S2)

유형	난이도	완료일	링크	특이사항
DFS, BFS	실버2	23/03/28	https://www.acmicpc.net/problem/1260

 

 

내 코드

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

using namespace std;

int arr[1001][1001];
int visited[1001];
int visited2[1001];
int n, m, v;
int cnt = 0;
int cnt2 = 1;

void DFS(int start)
{
	cnt++;
	if(cnt>n)
		return;
	
	cout << start<< " ";
	
	for(int i = 1; i<=n; i++)
	{
		if(arr[start][i]==1 && visited[i]==0)
		{
			visited[i] = 1;
			DFS(i);
			
		}
	}
}

void BFS(int start)
{	
	queue<int> q;
	q.push(start);
	visited2[start] = 1;
	
	while(!q.empty())
	{
		int target = q.front();
		q.pop();
		cout<<target<<" ";
		cnt2++;
		if(cnt2>n)
			break;
		
		for(int i= 1; i <= n; i++)
		{
			if(arr[target][i] == 1 && visited2[i] == 0)
			{
				q.push(i);
				visited2[i] = 1;
			}
		}
	}
}

int main(void)
{
	
	cin >> n >> m >> v;
	
	int v1, v2;
	for(int i= 0; i<m; i++)
	{
		cin >> v1 >> v2;
		arr[v1][v2]=1;
		arr[v2][v1]=1;
	}
	
	visited[v]=1;
	DFS(v);
	cout<<"\\n";	
	BFS(v);
	
}

제목 그대로 BFS와 DFS를 이용해서 그래프를 탐색하는 문제다. 나는 그래프를 2차원 배열로 표현하고 dfs는 재귀함수를 이용하여, bfs는 큐를 이용하여 구현했다. dfs는 다른 문제를 풀면서도 여러번 사용했어서 쉽게 구현했는데 BFS는 자주 써보지 않아서 헷갈렸다. 재귀적으로 함수를 짜려고 했으나 말이 안됐고 큐를 이용해서 만들 수 있었다.