글 읽기 - 2610번 회의실 배정 도저히 이해가안갑니다.

steve11344 6년 전 0

문제에서 위원회의 모든 참가자들의 대표자와 의사소통 거리가 가장 최소가 되도록 하라고 하였습니다.

따라서, 저는 bfs를 이용하여 위원회 내에서 어떤 사람이 대표자가 되었을때, 가장 의사소통 거리를 구해서 저장했습니다.

그리고, dfs를 이용하여 싸이클을 돌면서, 위원회의 수와 앞에서 구한 정보로 해당 위원회에 속한 사람들 중, 가장 먼 의사소통의 거리가 최소가 되는 사람을 구했습니다.

도저히 답이 안나와서 질문을 봤는데도, 저랑 비슷한 사람이 많았습니다. 이 문제를 푸는데 범한 오류가 있으면 알려주시고, 또한, 이 방법이 틀리고 플로이드와샬 알고리즘을 써야한다면, 왜 그런지 이유도 알려주시면 감사하겠습니다 ㅠㅠ

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n,k,a,b,ans=0;
vector<int> vec[105];
vector<int> res;
queue<int> q;
int visit[105];
int child[105];

int max(int a,int b){return a>b?a:b;}

int cc(int cur){
    visit[cur] = 0;
    q.push(cur);
    int tmp,ret=0;
    while(!q.empty()){
        tmp = q.front();
        q.pop();
        for(int i =0 ; i< vec[tmp].size(); i++){
            if(visit[vec[tmp][i]] > visit[tmp]+1){
                visit[vec[tmp][i]] = visit[tmp]+1;
                ret = max(ret,visit[vec[tmp][i]]);
                q.push(vec[tmp][i]);
            }
        }
    }
    return ret;
}

void solve(int cur){
    if(child[ans] > child[cur]) ans = cur;
    visit[cur] = 1;
    for(int c : vec[cur]){
        if(!visit[c]) solve(c);
    }
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i =0 ; i < k; i++){
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    child[0] = 1e9;
    for(int i =1 ; i<=n; i++){
        for(int j = 0 ; j <= 100; j++) visit[j] = 1e9;
        child[i] = cc(i);
    }
    memset(visit, 0, sizeof visit);
    int cnt =0;
    for(int i = 1; i<=n; i++){
        if(visit[i] == 0){
            cnt++;
            ans =0;
            solve(i);
            res.push_back(ans);
        }
    }
    cout << cnt << endl;
    for(int i =0  ;i < res.size(); i++) cout << res[i] <<endl;
    return 0;
}

koosaga 6년 전 1

첫째 줄에는 구성되는 위원회의 수 K를 출력한다. 다음 K줄에는 각 위원회의 대표 번호를 작은 수부터 차례로 한 줄에 하나씩 출력한다.

라고 써져있네요

steve11344 6년 전 0

감사합니다..도저히 이해가 안되서 문제를 몇번이고 읽었는데 출력부분은 제대로 읽지못해서 이런 경우가 발생했네요 ㅠㅠ 도움주셔서 감사합니다! 바로 해결했습니다.

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

문제

문제

출처

ICPC

2610번 회의실 배정 도저히 이해가안갑니다.

steve11344 6년 전 0

koosaga 6년 전 1

steve11344 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말