글 읽기 - 문제를 제대로 이해한 것이 맞나요??

dsa2341 5년 전 0

플루이드 알고리즘을 써서 arr의 전체값을 구한 후 그룹을 나누고 각 그룹의 인원마다 배열의 최댓값을 구해준다음

그룹 별로 그 최댓값이 가장 작은 번호를 출력한다. 이렇게 생각하고 풀었는데 왜 틀린지 모르겠습니다

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
#define MIN(a,b)	(((a)<(b))? (a):(b))
using namespace std;
int arr[101][101];
int group[101];
vector<pair<int, int>>res[101];
int main(void)
{
	int n, m, a, b, num=0;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) arr[i][j] = i == j ? 0 : INF;
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		arr[b][a]=arr[a][b] = 1;
	}
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				arr[i][j] = MIN(arr[i][j], arr[i][k] + arr[k][j]);
	for (int i = 1; i <= n; ++i) {
		int max=-1;
		if (group[i] == 0) ++num;
		for (int j = 1; j <= n; ++j) {
			if (arr[i][j] != INF) {
				if (arr[i][j] > max) max = arr[i][j];
				if(group[j]==0)group[j] = num;
			}
		}
		res[num].push_back({ max,i });
	}
	cout << num <<"\n";
	for (int i = 1; i <= num; ++i) {
		sort(res[i].begin(), res[i].end());
		cout << res[i][0].second << "\n";
	}
	return 0;
}

djm03178 5년 전 1

n이 작아서 시간 초과는 나지 않지만, 로직이 틀렸습니다.

25번째 줄에서 i번째 참석자가 아직까지 어떠한 그룹에도 속하지 않았으면 새로운 그룹 번호를 부여하고 있는데, 그렇지 않은 경우 기존의 group[i] 값을 사용해야 하지만 기존의 num을 사용해서 i에 연결된 j들에 대해 group[i]가 아닌 num을 부여해주게 됩니다.

djm03178 5년 전 1

그것만이 문제가 아니고,

이미 말씀드린 대로, group[j]들에 group[i]에 부여되어야지, num이 부여되면 안 됩니다. 그 전에 25번째 줄에서 group[i]에 그 번호가 들어가야겠죠.
만들어진 그룹 순서대로 최댓값의 최솟값의 번호를 찾아서 출력하면 되는 것이 아니라, 이들의 번호를 다시 오름차순으로 정렬해서 출력해야 합니다. 즉, 1번 그룹의 대표가 5이고 2번 그룹의 대표가 4이면 4 5 순으로 출력해야 합니다.

dsa2341 5년 전 0

말씀해주신 2번은 제가 아예 지나쳤었네요 정말 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

문제를 제대로 이해한 것이 맞나요??

dsa2341 5년 전 0

djm03178 5년 전 1

djm03178 5년 전 1

dsa2341 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말