글 읽기 - bfs 로 풀어서 통과했는데, 고쳐야 할 점 있나요 ? ?

kangsy763 4년 전 0

플로이드 와샬이라는 알고리즘의 존재 유무를 모르고 bfs로 풀었는데, 코드가 너무 먼길 돌아서 푸는 것 같고 로직이 복잡하지는 않지만, 배열도 너무 많이쓰고 하는 것이 영 걸리네요.. 고쳐야 할 부분 있으면 지적 부탁드리겠습니다.

그리고 이런 문제는 플로이드 와샬로 푸는 것이 제일 일반적인 방법인가요 ?

#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int user[100][100];
int kevin[100];
int visit[100];
int weight[100];
int u,line;
vector<pair<int, int> >vp;
queue<int> q;
int z;

bool cmp(pair<int,int> a, pair<int,int> b) {
	if (a.second == b.second) return a.first < b.first;
	else return a.second < b.second;
}

void bfs(int start) {
	q.push(start);
	visit[start] = 1;
	while (!q.empty()) {
		int x = q.front();
		kevin[z] += weight[x];
		q.pop();
		for (int i = 0; i < u; i++) {
			if (user[x][i] == 1 && visit[i] == 0) {
				q.push(i);
				weight[i] = weight[x] + 1;
				visit[i] = 1;
			}
		}
	}
}

int main() {
	scanf("%d %d", &u, &line);
	while (line--) {
		int a, b;
		scanf("%d %d", &a, &b);
		user[a-1][b-1] = 1;
		user[b-1][a-1] = 1;
	}
	for (z = 0; z < u; z++) {
		weight[z] = 1;
		bfs(z);
		vp.push_back(make_pair(z, kevin[z]));
		memset(visit, 0, sizeof(visit));
		memset(weight, 0, sizeof(weight));
	}
	sort(vp.begin(), vp.end(), cmp);
	printf("%d", vp[0].first+1);
	return 0;
}

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

문제

문제

출처

ICPC

bfs 로 풀어서 통과했는데, 고쳐야 할 점 있나요 ? ?

kangsy763 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말