글 읽기 - bfs로 구현했는데 틀렸다고 나옵니다..

rnjswnd1501 4년 전 0

이어진 관계를 방향성을 고려하여 vector에 넣어주었습니다.

그 후, queue가 각각의 node를 탐색하고 끝났을 때 해당 visit 배열의 true 갯수를 세주었습니다.

sort를 이용하여 정렬해주었으며, class의 cnt를 가지고 비교할 수 있도록 구현해보았습니다.

answer 벡터에 저장 후, 0번째와 비교하여 같은 cnt의 idx만 출력하여 결과를 확인했습니다.

주어진 예시와 질문 검색 게시판의 몇몇 반례들을 넣어보았는데 맞게 출력이 되었습니다...

어디가 잘못된걸 까요??

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int n, m, sp, ep;
vector<int> v[10001];
bool visit[10001];

class node {
public:
	int idx, cnt;
};

int bfs(int index) {
	queue<int> q;
	q.push(index); visit[index] = true;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int i = 0; i < v[cur].size(); i++) {
			int idx = v[cur][i];
			if (visit[idx])continue;
			visit[idx] = true;
			q.push(idx);
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (visit[i])cnt++;
	}
	return cnt;
}

bool desc(node a, node b) {
	return a.cnt > b.cnt;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> sp >> ep;
		v[ep].push_back(sp);
	}
	vector<node> answer;
	for (int i = 1; i <= n; i++) {
		memset(visit, false, sizeof(visit));
		node n1;
		n1.idx = i, n1.cnt = bfs(i);
		answer.push_back(n1);
	}
	sort(answer.begin(), answer.end(), desc);
	for (int i = 0; i < n; i++) {
		if (answer[0].cnt == answer[i].cnt) cout << answer[i].idx << " ";
	}
	return 0;
}

wjsqjawns 4년 전 0

desc 함수에서,

a.cnt와 b.cnt가 같을 때에 idx가 작은 쪽을 앞으로 가게 하면 정답 처리가 됩니다.

rnjswnd1501 4년 전 0

bool 함수를 어떻게 수정하면 가능한가요??

wjsqjawns 4년 전 0

이런 식으로 바꾸시면, cnt가 같을 때 idx가 작은 node가 앞으로 가게 정렬돼요.

bool desc(node a, node b) {
	if(a.cnt==b.cnt)
		return a.idx<b.idx;
	else
		return a.cnt>b.cnt;
}

rnjswnd1501 4년 전 1

감사합니다~~ 덕분에 해결되었습니다.

코딩도 한 수 배우고 갑니다!!! 좋은 하루 되세요~~~

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

문제

문제

출처

ICPC

bfs로 구현했는데 틀렸다고 나옵니다..

rnjswnd1501 4년 전 0

wjsqjawns 4년 전 0

rnjswnd1501 4년 전 0

wjsqjawns 4년 전 0

rnjswnd1501 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말