글 읽기 - 2660번 풀이중 2번째 시도에 맞았는데, 수정 코드중 질문드립니다.

thyung 4년 전 0

저는 먼저 처음에 모두의 점수를 50점이라고 한 뒤, 플로이드 워셜 알고리즘을 통해 최단경로를 구하고 그 점수를 기록했습니다. 이후 최저점이 갱신될 때마다 회장후보 벡터를 초기화하고 다시 추가해줬습니다.

처음에 틀려서 2번째 제출때 14-16줄과 26-28줄을 추가했습니다. 이렇게 하니 맞았는데 제가 잘 이해하고 푼건지 궁굼해서 질문드리게 되었습니다.

결론적으로 답에 영향을 미친것이 2->5로 가는 경로에서 2->3+3->5 , 2->5+5->5 에서 후자의 방법이 더 작을 때 , 저 두 부분을 안 하면 후자가 더 크게 되어 답이 틀리게 되는 거라고 이해했습니다. 제가 생각한 부분이 맞을까요?

맞다면 플로이드 워셜 알고리즘에서 해당 부분은 꼭 써줘야 하는거겠죠?

답변 미리 감사드립니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int group[51][51];//그룹 정보
int max_score[51];//각 사람들의 점수
vector<int> vc;//회장 후보
int minimum=50;//회장후보의 점수
int main() {
	int n;
	int a, b;
	cin >> n;
	fill(&group[0][0], (&group[50][50]) + 1, 50);
	for (int i = 1; i <= n; i++) {
		group[i][i] = 0;
	}
	while (1) {
		cin >> a >> b;
		if (a == -1 && b == -1) break;
		group[a][b] = 1;
		group[b][a] = 1;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					continue;
				}
				if (group[i][j] > group[i][k] + group[k][j]) {
					group[i][j] = group[i][k] + group[k][j];
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		int each_max = 0;
		for (int j = 1; j <= n; j++) {
			each_max = each_max > group[i][j] ? each_max : group[i][j];
		}
		max_score[i] = each_max;
		if (minimum > max_score[i]) {
			minimum = max_score[i];
			vc.clear();
			vc.push_back(i);
		}
		else if (minimum == max_score[i]) {
			vc.push_back(i);
		}
	}
	cout << minimum << ' ' << vc.size()<< '\n';
	for (int i = 0; i < vc.size(); i++) {
		cout << vc[i] << ' ';
	}
}

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

문제

문제

출처

ICPC

2660번 풀이중 2번째 시도에 맞았는데, 수정 코드중 질문드립니다.

thyung 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말