글 읽기 - 1260번 DFS BFS 구하는 문제 왜 틀렸는지 모르겠습니다 도와주세요ㅠㅠ

snrnsl2 5년 전 0

왜 틀렸는지 도저히 모르겠습니다... 도와주세요ㅠ

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int grape[20000][2];
bool visit[1001];
bool visit2[1001];

int main()
{
	stack<int> s;
	queue<int>q;
	int v, e, start, v1, v2;
	scanf("%d %d %d", &v, &e, &start);

	for (int i = 0; i < e; ++i)
	{
		scanf("%d %d", &v1, &v2);
		// 양방향 간선을 한 방향씩 넣어준다
		grape[2 * i][0] = v1;
		grape[2 * i][1] = v2;

		grape[2 * i + 1][0] = v2;
		grape[2 * i + 1][1] = v1;
	}

	///////////////////DFS 구하기
	s.push(start);
	visit[start] = true;
	printf("%d", start);

	int min = 0;
	while (s.size() > 0)
	{
		int cur = s.top();
		min = v+1;

		for (int i = 0; i < e * 2; ++i)
		{
			if ((grape[i][0] == cur) && (grape[i][1] < min) && (visit[grape[i][1]] == false))
				min = grape[i][1];
		}

		// 방문할 수 있는 정점을 찾은 경우
		if (min != v + 1)
		{
			printf(" %d", min);
			visit[min] = true;
			s.push(min);
		}
		else
		{
			s.pop();
		}
	}

	printf("\n");

	///////////////////BFS 구하기
	q.push(start);
	visit2[start] = true;
	printf("%d", start);

	while (q.size() > 0)
	{
		int cur = q.front();

		for (int i = 0; i < e * 2; ++i)
		{
			if ((grape[i][0] == cur) && (visit2[grape[i][1]] == false))
			{
				printf(" %d", grape[i][1]);
				q.push(grape[i][1]);
				visit2[grape[i][1]] = true;
			}
		}

		q.pop();
	}

	return 0;
}

cafemug 5년 전 0

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다

이 조건을 만족시켜주는 코드가 없어보입니다

snrnsl2 5년 전 1

확인해보니 BFS를 구할 때 말씀해주신대로 작은 것부터 방문하는 조건을 구현하지 않았네요ㅠㅠ

답변해주셔서 감사합니다!!

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

문제

문제

출처

ICPC

1260번 DFS BFS 구하는 문제 왜 틀렸는지 모르겠습니다 도와주세요ㅠㅠ

snrnsl2 5년 전 0

cafemug 5년 전 0

snrnsl2 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말