글 읽기 - dfs, bfs 질문입니다.

jh06038 2년 전 0

예시대로 해서 올바른 정답이 나왔고, 디버그 상으로도 오류가 없었는데 오답으로 판정이 나서 어디에서 틀렸는지 모르겠습니다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
void DFS(const vector<vector<int>>& arr, int start) {
	vector<bool> visit(arr.size());	vector<int> seq; stack<int> s;
	visit[start - 1] = true;
	seq.push_back(start);
	s.push(start);
	while (!s.empty()) {
		for (int i = 0; i < arr[start - 1].size(); i++) {
			if (arr[start - 1][i] == 1 && !visit[i]) {
				s.push(i + 1);
				visit[i] = true;
				seq.push_back(i + 1);
				start = i + 1;
				i = 0;
				break;
			}
		}
		s.pop();
	}
	for (int i = 0; i < seq.size(); i++)
		cout << seq[i] << " ";
}
void BFS(const vector<vector<int>>& arr, int start) {
	vector<bool> visit(arr.size());	vector<int> seq; queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int front = q.front();
		if (!visit[front - 1])
			seq.push_back(front);
		q.pop();
		visit[front - 1] = true;
		for (int i = 0; i < arr[front - 1].size(); i++) {
			if (arr[front - 1][i] == 1 && !visit[i])
				q.push(i + 1);
		}
	}
	for (int i = 0; i < seq.size(); i++)
		cout << seq[i] << " ";
}
int main() {
	int N, M, V, a, b;	cin >> N >> M >> V;
	vector<vector<int>> arr;
	for (int i = 0; i < N; i++) {
		vector<int> tmp(N);
		arr.push_back(tmp);
	}
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		a -= 1; b -= 1;
		arr[a][b] = 1;	arr[b][a] = 1;
	}
	DFS(arr, V);
    cout << '\n';
	BFS(arr, V);

	return 0;
}

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

문제

문제

출처

ICPC

dfs, bfs 질문입니다.

jh06038 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말