[BOJ]1260-DFS와 BFS

1260

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool visited[1001];
bool graph[10001][10001];

int node{ 0 }; // 정점의 개수 N(1 ≤ N ≤ 1,000)
int edge{ 0 }; // 간선의 개수 M(1 ≤ M ≤ 10,000)
int start{ 0 }; //탐색을 시작할 정점의 번호 V

void dfs(int x)
{
	visited[x] = true;
	cout << x << " ";
	for (int i = 1; i <= node; i++)
	{
		if (graph[x][i] && !visited[i])
			dfs(i);
	}
}

void bfs(int start)
{
	queue <int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		cout << x << " ";

		for (int i = 1; i <= node; i++)
		{
			if (!visited[i] && graph[x][i])
			{
				q.push(i);
				visited[i] = true;
			}
		}
	}
}

int main() {

	cin >> node >> edge >> start;

	for (int i = 0; i < edge; i++)
	{
		int a{ 0 };
		int b{ 0 }; 

		cin >> a >> b;
	
		graph[a][b] = true;
		graph[b][a] = true;
	}

	for (int i = 1; i <= node; i++)
		visited[i] = false;

	dfs(start);

	cout << endl;

	for (int i = 1; i <= node; i++)
		visited[i] = false;

	bfs(start);

	return 0;
}

처음 DFS와 BFS 이론을 보고 그래프를 vector로 push_back으로 해당 간선을 넣었는데 테스트케이스에는 1부터 탐색하는 방향이어서 틀렸다.

그래서 1260 답을 찾아보고 이중 배열로 그래프를 처리해 앞에서부터 찾아나가는 방식으로 고쳤다.

런타임 에러 -> 틀림 -> 정답!

참고자료

---

DFS와 BFS 이론
1260 답