정올 초등_ 회장뽑기 KOI 1997

이번에 풀어본 문제는  초등부 정올  회장뽑기 문제입니다.

처음엔 문제 내용부터 이해가 잘 안가서  고생했는데,  입력예시랑 결과 보고  다시 문제보니까 이해했습니다.

단순 BFS문제였고  각 회원마다  점수들 저장시켜서  최종적으로  가장 적은 점수 가진사람들 출력하면 끝나는 쉬운 문제였습니다.

 

codeup.kr/problem.php?id=4433

회장뽑기

 

 

#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

struct info{
	int number;
	int score;	
};

bool cmp(struct info a , struct info b){
	if(a.score == b.score) {
		return a.number < b.number;	
	}
	
	return (a.score<b.score);
}

int main()
{
	struct info scoreboard[51]={};
	int relation[51][51]={};
	int n;
	scanf("%d",&n);
		
	//-1 -1전까지 받기
	
	int x=0,y=0;
	while(x!=-1 && y!=-1){
		scanf("%d %d",&x,&y);
		
		//1. 그래프 형태로 표현  
		relation[x][y] = 1;
		relation[y][x] = 1;
			
		//relation[x][y] = relation[y][x] = 1;
	}
	
	for(int man=1;man<=n;man++){
		int discover[51]={};
		queue<pair<int,int> > que;
		
		que.push(make_pair(man,0));
		discover[man] = 1;
		
		int score=0;
		while(!que.empty()){
			pair<int,int> ft = que.front();
			que.pop();
			
			if(score < ft.second){
				score = ft.second;	
			}
			
			for(int i=1;i<=n;i++){
				if(relation[ft.first][i] == 1 && discover[i] == 0){
					que.push(make_pair(i,ft.second+1));
					discover[i] = 1;
				}
			}
			
		}
		scoreboard[man]= {man,score};
	}
	
	sort(scoreboard+1,scoreboard+n+1,cmp);
	
	int minScore = scoreboard[1].score;
	int answerCnt=0;
	
	int i=1;
	
	while(minScore == scoreboard[i].score){
		answerCnt++;
		i++;	
	}
	printf("%d %d\n",minScore,answerCnt); 
	for(int j=1;j<=answerCnt;j++){
		printf("%d ",scoreboard[j].number);
	}
	
	return 0;	
}

 

 

무편집본 영상

youtu.be/2JwoE0x4e4E