[Baekjoon] 19538_루머

Gold IV

문제(출처: https://www.acmicpc.net/problem/19538)

---

< 루머 >

 

문제 풀이

 

bfs를 통해 주변 사람을 탐색하며 자신이 루머를 믿기 시작했을 때 자신의 이웃들에게 루머를 믿는다는 것을 알려준다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _19538_ { // 루머
	static ArrayList<ArrayList<Integer>> arr;
	static int visited[];
	static int result[];
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int n=Integer.parseInt(bf.readLine()); // 사람의 수
		result=new int[n]; // 루머를 믿기 시작한 시간
		arr=new ArrayList<>(); // 이웃
		visited=new int[n]; // 방문 여부
		for(int i=0; i<n; i++) {
			arr.add(new ArrayList<>());
			result[i]=-1;
		}
		
		// 주변인들을 인접 리스트로 저장
		for(int i=0; i<n; i++) {
			st=new StringTokenizer(bf.readLine());
			while(st.hasMoreTokens()) {
				int num=Integer.parseInt(st.nextToken())-1;
				if(num!=-1) {
					arr.get(i).add(num);
				}
			}
		}
		
		// 최초 유포자 후
		int person=Integer.parseInt(bf.readLine());
		st=new StringTokenizer(bf.readLine());
		
		Queue<int[]>queue=new LinkedList<>();
		for(int i=0; i<person; i++) {
			int a=Integer.parseInt(st.nextToken())-1;
			queue.add(new int[] {a, 0});
		}
		
		bfs(queue);
		
		for(int i=0; i<n; i++) {
			bw.write(result[i]+" ");
		}
		bw.flush();
		
	}
	private static void bfs(Queue<int[]> queue) {
		
		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			if(result[temp[0]]>-1) continue;
			result[temp[0]]=temp[1];
			for(int i=0; i<arr.get(temp[0]).size(); i++) {
				int num=arr.get(temp[0]).get(i);
				visited[num]+=1;
				if(result[num]==-1 && visited[num] >= (double)arr.get(num).size()/2 ) {
					queue.add(new int[] {num, temp[1]+1});
				}
			}
			
		}
	}
}

 

Main

- 사람의 수 (n) 입력

- result : 루머를 믿기 시작한 시간 저장

  arr : 이웃을 인접 리스트로 저장

  visited : 이웃들의 루머 믿는 인원

- 주변인들을 인접 리스트로 저장

- 최초 유포자 수(m) 입력 및 최초 유포자 번호를 queue에 저장

- bfs 함수 호출 후 result 배열 출력

 

bfs

- queue가 빌 때까지 반복 -> 이미 루머를 믿기 시작했다면 밑에 코드 수행 x / 아직 루머를 믿지 않는다면 루머 믿는 시간 저장 후 이웃들 탐색 -> 이웃들에게 자신이 루머를 믿는다고 알림 -> 주변인의 절반 이상이 루머를 믿는다면 queue에 추가

 

---

생각🤔

 

처음에는 자신이 루머를 믿게 된 후 주변인들에게 알리는 것이 아닌 자신을 기준으로 주변인들이 루머를 믿는가 안 믿는가를 판별하여 while문 안에 2중 for문으로 구현하였다. 그 결과 시간초과가 발생했다. 

---