글 읽기 - C++ 반례 많이 찾아봤는데 안되네요 한 번 만 도와주세요 흑

tina0430 5년 전 0

반례도 찾아서 넣어보고 다 맞아서 제출했는테 틀렸습니다 뜹니다 ㅜㅜ 왜그럴까요 뭐가 문제인지 잘 모르겠습니다.

https://www.acmicpc.net/board/24356

여기에 나온 반례도 다 집어넣었는데 맞다고 뜨더라구요 허허..

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

int main () {
	int N, M, V;
	int i;
	int v1, v2; //정점쌍

	cin >> N >> M >> V;
	vector < set <int> > nodes(N);
	bool *visited = new bool[N]; //기본값 = true

	vector <int> result;

	for (i = 0 ; i < M ; i++){
		cin >> v1 >> v2;
		nodes[v1-1].insert(v2-1);
		nodes[v2-1].insert(v1-1); //양방향 이니까
	}

	vector < set <int> > nodes2 = nodes;

	//dfs
	stack<int> node_stack;
	node_stack.push(V-1);
	int v;

	while(!node_stack.empty()) {
		v = node_stack.top();
		node_stack.pop();

		if (visited[v]) {
			result.push_back(v+1);
			visited[v] = false;
		}
		
		set<int>::reverse_iterator riter;
		for (riter = nodes[v].rbegin(); riter != nodes[v].rend(); riter++)
			node_stack.push(*riter);
		nodes[v].clear();
	}

	for(auto &n : result)
		cout << n << " ";
	cout << endl;

	result.clear();
	
	for (i = 0 ; i < N ; i++ )
		visited[i] = true;

	//bfs
	queue<int> node_queue;
	node_queue.push(V-1);

	while(!node_queue.empty()) {
		v = node_queue.front();
		node_queue.pop();

		if (visited[v]){
			result.push_back(v+1);
			visited[v] = false;
		}
		
		for (auto &n : nodes2[v])
			node_queue.push(n);

		nodes2[v].clear();
	}

	for(auto &n : result)
		cout << n << " ";
	cout << endl;
}

betain24 5년 전 0

문제에 보면 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 라고 조건이 하나 더 있습니다. 위의 코드에서는 작은 정점부터 방문하는게 아니라 그냥 입력받은 순서대로 탐색을 하네용

그 부부만 고치면 될거같습니다.

tina0430 5년 전 0

set은 insert()로 추가하면 자동으로 오름차순 정렬하는것으로 알고 있어 저렇게 짜도 작은 정점부터 방문하는걸로 이해했는데 혹시 제가 잘못 이해한걸까요?

betain24 5년 전 1

으억.. 찾았다

저거 사실 기본값 true 아닙니다 ..ㅋㅋ

저거 찍어보면 랜덤값이 나오네요..

dfs전에 초기화해주면 맞네요

for (i = 0 ; i < N ; i++ ) visited[i] = true;

bool *visited = new bool[N]; //기본값 = true

tina0430 5년 전 0

와 betain24 님 사랑해여 너무 감사합니다.

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

문제

문제

출처

ICPC

C++ 반례 많이 찾아봤는데 안되네요 한 번 만 도와주세요 흑

tina0430 5년 전 0

betain24 5년 전 0

tina0430 5년 전 0

betain24 5년 전 1

tina0430 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말