[9주차_화요일] 회장 뽑기

[Jewan1120]

• 사이트 : 백준(BOJ)
• 문제: 회장 뽑기
• 번호: 2660

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[baexxbin]

🤔 시간복잡도 고려사항

• 회원의 수 <= 50
• 인접리스트 BFS: 50*(50+50)..?
• 완전탐색 가능

💡 풀이 아이디어

• 각 회원의 친구 점수 계산하기 (BFS)
  • bfs를 통해 가장 먼 친구 거리를 구해 최종 친구 점수 반환
• 회장 점수 구하기 (mn)
  • 친구 점수 배열(ans)의 최소값 구하기
• 회장 후보 수와 후보 구하기
  • 친구 점수 배열(ans)에서 mn인 개수 구하고, mn값인 후보 출력

[Jewan1120]

🤔 시간복잡도 고려사항

• 회원의 수는 50명을 넘지 않는다.
• 널널해서 따로 고려하지 않았음

💡 풀이 아이디어

• 각 인원의 점수는 가장 멀리 떨어져 있는 친구와의 거리
• 모든 회원들 사이의 최단 거리를 구해줘야함 → 플로이드 와샬
• 최단 거리 계산 후, 회원들 사이에서 최소 최단거리를 가지는 회원들을 선택

  BFS도 가능하지만 플로이드 와샬 문제였씀다!

[yeongleej]

🤔 시간복잡도 고려사항

• 회원수 N <= 50

=> 최대 친구사이(간선수) : N-1 => 다익스트라 사용시, O((N-1) log N) => N이 충분히 작으므로 완전탐색도 가능

💡 풀이 아이디어

• 다익스트라: 한 회원으로부터 다른 회원들까지의 거리를 구해서 가장 큰 거리가 점수가 됨
  • 각 회원부터 다른 회원들까지의 최단거리를 구함
  • 점수는 해당 회원으로부터 가장 멀리 떨어진 회원까지의 거리가됨
  • 점수가 가장 작은 회원들의 리스트 구함

[KodaHye]

🤔 시간복잡도 고려사항

• 회원의 수 <= 50
• 회원의 수가 적기 때문에 각 회원마다 친구 관계가 어떻게 되는지 모든 경우를 찾아도 될 것이라고 생각함
• BFS를 통한 풀이: 50 * (50 + 간선의 수)

💡 풀이 아이디어

• 문제 주건에 몇 사람을 통하면 모두 서로 알 수 있다는 조건이 있기 때문에, 모두 연결이 된 그래프라는 것을 알 수 있음 (동 떨어진 경우 고려하지 않아도 됨)
• 회원의 점수는 자신이 모든 친구들을 탐색했을 때, 최대 깊이와 같음
• 회장이 될 수 있는 사람은 최대 깊이가 가장 작은 사람이 됨

[icegosimperson]

🤔 시간복잡도 고려사항

• N(회원의 수) <=50 : O(N^3) (50^3 : 가능)

💡 풀이 아이디어

• 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램 작성
• 점수 : 특정 회원이 다른 모든 회원과 연결되기 위해 필요한 최단 거리 중에서 가장 먼 거리
• 회장 : 점수가 가장 낮은 사람(가장 가까운 거리에 있는 사람 = 최단거리) 구해야 함
• 조건 : 몇 사람을 통하면 모두가 서로알 수 있다 = 모든 회원(노드)가 연결되어 있음 -> 플로이드

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 다익스트라
• 시간복잡도: 회원의 수 <= 50 회원 1명 당 최대 간선수 N-1 > 50-1 회원 별로 모든 연결 간선을 찾으며 가중치 순으로 정렬하므로 O(N*(N-1)logN) > 약 O(N^2logN)

💡 풀이 아이디어

• 점수 획득 방법
  • 특정 사람을 기준으로 1점:친구 2점:친구의 친구 3점:친구의 친구의 친구

노드	연결된 노드	1	2	3	4	5
1	2	0	1	2	2	3
2	1, 3, 4	1	0	1	1	2
3	4, 2, 5	2	1	0	1	1
4	2, 3, 5	2	1	1	0	1
5	3, 4	3	2	1	1	0

• 각 회원 별로 연결된 간선을 이어가면서 다음 간선까지의 거리를 구하기 위해 가중치 +1 하기
  • Node(연결된 친구,거리)

    for(int friend : graph.get(person.index)){
    if(table[friend] > table[person.index]+1){ 
     table[friend] = table[person.index]+1;
     queue.offer(new Node(friend,table[friend]));  
    }
    }

• 회장은 각 회원들의 최고 가중치 중 점수가 가장 작은 사람이 된다.