반응형
https://www.acmicpc.net/problem/2660
2660번: 회장뽑기
입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터
www.acmicpc.net
소스코드
풀이
★ 문제를 읽었을 때 이해하기가 조금 난해할 순 있지만 해당 회원 번호에서 모든 회원과 친구가 되기 위해서 몇번동안 BFS 안의 과정을 거쳐야 하는지 구해주시면 됩니다 !
★ 점수를 구하기 위해 큐에 회원번호와 점수를 기록하는 수를 함께 추가하였습니다. 이 점수는 BFS 안에서 큐에 추가되는 과정마다 다른 루트로 이동하기 때문에 1씩 증가하게 됩니다.
예시 1번에서
1,2
2,3
3,4
4,5
2,4
=> [2], [1,3,4], [2,4,5], [3,5,2], [4,3] 형태의 친구관계가 만들어집니다.
이때 회원 번호로 2가 들어온 경우 2와 친구인 1,3,4를 통해 점수가 1점이 되게 되고, 아직 5와 친구가 아니기 때문에 방문하지 않은 루트를 다시 방문해줘야 합니다. 3번 루트를 방문했을 때 5까지 방문할 수 있기 때문에, 이 상황에서 모든 번호와 친구가 되고, 점수는 2가 되게 됩니다 !
★ 그 후 점수가 기록되어 있는 count 배열 안에서 회장 후보 점수와 후보 수, 후보 번호를 차례대로 출력해주시면 됩니다 :)
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 2346번: 풍선 터뜨리기 (Python) (0) | 2023.10.18 |
|---|---|
| [백준 알고리즘] 2776번: 암기왕 (Python) (0) | 2023.10.17 |
| [백준 알고리즘] 4358번: 생태학 (Python) (0) | 2023.10.16 |
| [백준 알고리즘] 16948번: 데스 나이트 (Python, BFS) (1) | 2023.10.16 |
| [백준 알고리즘] 1303번: 전쟁 - 전투 (Python, BFS) (0) | 2023.10.16 |