[백준 / BOJ] 19538 루머

문제

출처 : https://www.acmicpc.net/problem/19538

19538번: 루머

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: 백준 알고리즘 소스코드🙃