글 읽기 - C++ 89%에서 틀렸다고 나옵니다 (코드는 읽기 쉬우실듯)

betteryou 4년 전 1

질문에 올라온 반례는 모두 정상적으로 수행되는데

어디가 문제인건지 혹시 확인 가능하신 분 계신가요???

최대한 코드 깔끔하게 기능별로 나눠놨는데

확인부탁드립니다

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class node {
public :
	int data;
	vector<node*> edge;
};

bool cmp(node* a, node* b) {
	if (a->data < b->data) return true;
	return false;
}

int read(vector<node>& arr,vector<bool>& visit) {

	arr.clear();
	visit.clear();

	int vertex, edge_num, start;
	cin >> vertex >> edge_num >> start;

	arr.resize(vertex + 1);
	visit.resize(vertex + 1,false);

	int a, b;				// a에서 b로 가는 간선
	for (int i = 0;i < edge_num;i++) {
		cin >> a >> b;

		arr[a].data = a;
		arr[b].data = b;

		arr[a].edge.push_back(&arr[b]);
		arr[b].edge.push_back(&arr[a]);
	}

	for (int i = 1; i <= vertex;i++) {			//방문할 수 있는 정점 번호를 오름차순으로 정렬
		sort(arr[i].edge.begin(), arr[i].edge.end(), cmp);
	}

	return start;
}


void dfs(node* nd, vector<bool>& visit) {
	if (visit[nd->data]) return;

	visit[nd->data] = true;

	cout << nd->data << ' ';
	
	for (int i = 0;i < nd->edge.size();i++) {
		dfs(nd->edge[i],visit);
	}
}

void bfs(node* nd, vector<bool>& visit) {
	queue<node*> Q;			//BFS를 수행하기 위한 Queue 선언
	
	Q.push(nd);
	visit[nd->data] = true;

	while (!Q.empty()) {
		node* nnd = Q.front();
		Q.pop();

		cout << nnd->data << ' ';
		
		for (int i = 0;i < nnd->edge.size();i++) {
			if (!visit[nnd->edge[i]->data]) {
				Q.push(nnd->edge[i]);
				visit[nnd->edge[i]->data] = true;
			}
		}
	}
}

int main() {
	
	vector<node> arr;		//그래프 저장
	vector<bool> visit;		// DFS, BFS 수행 시 탐색여부 저장
	
	int start = read(arr,visit);		//그래프 정보를 입력 한 후 탐색을 시작할 정점의 번호를 반환하여 저장

	dfs(&arr[start],visit);			//DFS를 수행한 결과를 출력
	cout << '\n';

	fill(visit.begin(), visit.end(), false);	//BFS를 수행하기 위해 탐색여부 초기화

	bfs(&arr[start],visit);			//BFS를 수행한 결과를 출력

	return 0;	
}

chw0501 4년 전 1

3 1 1

2 3

반례 드립니다.

betteryou 4년 전 0

@chw0501

시작점에서 이어진 간선이 없는 경우

출력안뜨게 하던가, 프로그램종료되게끔 했는데도 87%에서 틀렸다고 나오네요 ..

아래 소스는 질문글에 있는 소스에서 91행만 추가했어요

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class node {
public:
	int data;
	vector<node*> edge;
};

bool cmp(node* a, node* b) {
	if (a->data < b->data) return true;
	return false;
}

int read(vector<node>& arr, vector<bool>& visit) {

	arr.clear();
	visit.clear();

	int vertex, edge_num, start;
	cin >> vertex >> edge_num >> start;

	arr.resize(vertex + 1);
	visit.resize(vertex + 1, false);

	int a, b;				// a에서 b로 가는 간선
	for (int i = 0;i < edge_num;i++) {
		cin >> a >> b;

		arr[a].data = a;
		arr[b].data = b;

		arr[a].edge.push_back(&arr[b]);
		arr[b].edge.push_back(&arr[a]);
	}

	for (int i = 1; i <= vertex;i++) {			//방문할 수 있는 정점 번호를 오름차순으로 정렬
		sort(arr[i].edge.begin(), arr[i].edge.end(), cmp);
	}

	return start;
}


void dfs(node* nd, vector<bool>& visit) {
	if (visit[nd->data]) return;

	visit[nd->data] = true;

	cout << nd->data << ' ';

	for (int i = 0;i < nd->edge.size();i++) {
		dfs(nd->edge[i], visit);
	}
}

void bfs(node* nd, vector<bool>& visit) {
	queue<node*> Q;			//BFS를 수행하기 위한 Queue 선언

	if (nd->data == 0) return;

	Q.push(nd);
	visit[nd->data] = true;

	while (!Q.empty()) {
		node* nnd = Q.front();
		Q.pop();

		cout << nnd->data << ' ';

		for (int i = 0;i < nnd->edge.size();i++) {
			if (!visit[nnd->edge[i]->data]) {
				Q.push(nnd->edge[i]);
				visit[nnd->edge[i]->data] = true;
			}
		}
	}
}

int main() {

	vector<node> arr;		//그래프 저장
	vector<bool> visit;		// DFS, BFS 수행 시 탐색여부 저장

	int start = read(arr, visit);		//그래프 정보를 입력 한 후 탐색을 시작할 정점의 번호를 반환하여 저장

	if (arr[start].edge.empty()) exit(0);

	dfs(&arr[start], visit);			//DFS를 수행한 결과를 출력
	cout << '\n';

	fill(visit.begin(), visit.end(), false);	//BFS를 수행하기 위해 탐색여부 초기화

	bfs(&arr[start], visit);			//BFS를 수행한 결과를 출력

	return 0;
}

chw0501 4년 전 1

시작점에서 이어진 간선이 없는 경우에는 그 시작점을 방문하고(출력하고) 끝나는 겁니다. 한가지 해결 방법은 처음에 arr배열의 각 노드에 data값을 1~n까지 설정하는 것입니다:)

betteryou 4년 전 3

@chw0501

" 시작점에서 이어진 간선이 없는 경우에는 그 시작점을 방문하고(출력하고) 끝나는 겁니다. "

제가 위 부분에 대한 걸 누락했었네요. 몇 달만에 문제확인이 되었네요

말씀하신 해결법으로 해결되었습니다 감사합니다 :)

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

문제

문제

출처

ICPC

C++ 89%에서 틀렸다고 나옵니다 (코드는 읽기 쉬우실듯)

betteryou 4년 전 1

chw0501 4년 전 1

betteryou 4년 전 0

chw0501 4년 전 1

betteryou 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말