문제
출처 : https://www.acmicpc.net/problem/19538
19538번: 루머
예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$
www.acmicpc.net
N명이 사람이 있다.
이 N명의 사람은 어떠한 루머를 자신과 연관된 주변인중 절반이상이 믿는다면 자신또한 그 루머 믿는다.
이때, 모든 사람이 루머를 믿기위해서 걸리는 시간을 구하는 프로그램을 구하는 문제다.
충분히 많은 시간이 지나도 루머를 믿지 않을 경우 -1을 출력하면된다.
소스코드
기본적인 다익스트라 문제였다.
각 사람이 루머를 믿기시작한 최초시점을 배열에 저장하며 탐색하면 된다.
주요 소스코드
private void setRumor(){
while(!pq.isEmpty()){
Node node = pq.poll();
if(check[node.idx] <= node.cnt) continue;
check[node.idx] = node.cnt;
for(Integer nextIdx : list.get(node.idx)){
if(check[nextIdx] <= node.cnt+1) continue;
rumor[nextIdx]--;
if(2*rumor[nextIdx] < firRumor[nextIdx]) pq.add(new Node(nextIdx, node.cnt+1));
}
}
}
전체소스코드
https://github.com/devxb/JJUNalgo/blob/master/19538%20%EB%A3%A8%EB%A8%B8/Main.java
GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃
백준 알고리즘 소스코드🙃. Contribute to devxb/JJUNalgo development by creating an account on GitHub.
github.com
'알고리즘 (2020 : 08 : 10 ~ ) > 벨만포드,다익스트라,MST' 카테고리의 다른 글
[백준 / BOJ] 20010 악덕 영주 혜유 (Java) (0) | 2023.01.06 |
---|---|
[백준 / BOJ] 20183 골목 대장 호석 - 효율성 2 (Java) (0) | 2022.05.24 |
[백준 / BOJ] 17182 우주 탐사선 (완전탐색) (0) | 2021.08.24 |
[백준 / BOJ] 16137 견우와 직녀 (0) | 2021.08.16 |
[백준 / BOJ] 1854 K번째 최단경로 찾기 (0) | 2021.06.23 |