글 읽기 - c++ DFS/BFS 질문입니다.

kcsoo1234 2년 전 0

논리는 문제 없이 구현한 것 같습니다.

다만 가장 작은 수부터 조사를 해야하는데 이 부분은 아무리 생각해도 해결을 못하겠습니다.

혹시 힌트를 주실 수 있으실까요?

(만약 논리에 문제가 있다면 지적 부탁드립니다)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>

using namespace std;

bool checkbfs[10000];
bool checkdfs[10000];

void DFS(int start, vector<int>* g) {
	
	stack<int> s;
	s.push(start);
	checkdfs[start] = true;

	while (s.empty() == false) {
		int cur_node = s.top();
		s.pop();
		for (int i = 0; i < g[cur_node].size(); i++) {
			int next_node = g[cur_node][i];
			if (checkdfs[next_node] == false) {
				checkdfs[next_node] = true;
				s.push(next_node);
			}
		}
		cout << cur_node << ' ';
	}

}

void BFS(int start, vector<int>* g) {

	queue<int> q;
	q.push(start);
	checkbfs[start] = true;

	while (q.empty() == false) {
		int cur_node = q.front();
		q.pop();
		for (int i = 0; i < g[cur_node].size(); i++) {
			int next_node = g[cur_node][i];
			if (checkbfs[next_node] == false) {
				checkbfs[next_node] = true;
				q.push(next_node);
			}
		}
		cout << cur_node << ' ';
	}


}


int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, a, b, V;

	cin >> N >> M >> V;

	vector<int>* graph = new vector<int>[N+1];

	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}


	DFS(V, graph);
	cout << "\n";
	BFS(V, graph);

	
	return 0;
}

seungwuk98 2년 전 0

정점을 작은 것부터 방문해야하는 것 때문에 WA가 나는게 맞는것 같습니다. graph의 모든 원소를 정렬해주면 될 겁니다.

kcsoo1234 2년 전 0

감사합니다. 그렇다면 알고리즘 자체에는 문제가 없다는 말씀이신가요?

seungwuk98 2년 전 0

테스트는 안해보긴 했는데 눈으로 봤을땐 별로 문제가 없어보이네요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ DFS/BFS 질문입니다.

kcsoo1234 2년 전 0

seungwuk98 2년 전 0

kcsoo1234 2년 전 0

seungwuk98 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말