Baekjoon 2660 회장뽑기 JAVA

https://www.acmicpc.net/problem/2660

2660번: 회장뽑기

 

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202660

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 회원 간의 연결 정보가 주어졌을 때

연결된 수가 가장 작은 사람이 회장 후보가 되고

회장 후보가 되는 수와 후보 수, 후보들을 출력하는 문제다.

​

조건

어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다

​

해당 문제는 플로이드 와샬을 이용해서 해결했다.

입력 처리를 해주고 처음 map를 최댓값으로 갱신해 준다

​

이후 회원 간의 연결정보를 가지고 연결된 부분을 1로 처리해 준다 (양방향)

플로이드 와샬 알고리즘을 적용하고

각 행별로 최댓값을 구하고 그 행의 첫 번째 칸에 저장한다 map[i][0] 은 빈 공간

각 행별 최댓값 중 최솟값도 갱신한다.

​

이후 최솟값을 가지고 각행의 첫 번째 자리만 비교해서 큐에 넣어주고

최종적으로 최솟값 큐 사이즈를 출력하고

큐에서 하나씩 빼내서 출력해 주는데 반복문을 큐의 사이즈만큼 돌렸기 때문에

큐에서 poll 하면 큐 사이즈도 감소하기 때문에 i 값도 같이 1 감소시켜준다.