[Epper] 백준 19538 루머 java

문제

 귀찮아서 생략..

백준 문제와 달리 이퍼 시험에서는 메인 함수를 작성하지 않아도 되기 때문에 따로 입력받지 않고 그냥 예시에 나와있는 값으로 하였다.

또 풀이를 쉽게 하기 위해 처음에 0을 추가로 입력시켜 주었다. 

 

풀이

백준의 바이러스 문제와 비슷하게 감염을 시키는 문제이다. 이 문제 역시 bfs를 사용하여 풀 수 있다.

solution 함수에 대해서 설명하자면

answer은 반환할 정답 배열, turn은 몇명 이상이 감염되어야 i번 사람이 감염되는지 저장하는 배열이다.

turn 배열은 bfs를 진행하면서 i의 주변인이 감염되면 turn[i-1]-=1(배열 인덱스는 0부터 시작하기 때문에 -1을 해줌)을 해주고 이 값이 0이하가 되면 감염되는 코드이다.

 

answer배열을 -1로 초기화하는 이유는 해당 사람이 이미 감염되어 있는 상태였는지 아닌지 구분하기 위해 -1로 초기화해준다. (answer가 -1이 아니라면 이미 감염된 상태)

 

최초 생성자에 대한 연산을 먼저 처리 해주고

몇명 이상이 감염되어야 i번 사람이 감염되는지를 계산한다. 주변인의 절반 이상이 감염되었을 때 감염이 되기 때문에 adj[i].length/2 가 된다. 이때 메인 함수에서 처음에 0을 추가로 입력시켜 주었기 때문에 인덱스 값을 신경써주어야 한다.

 

큐가 empty가 되기 전까지 bfs 탐색을 진행한다. 이때 next가 0인 경우, 0 입력은 단순히 입력의 끝은 나타내주는 입력이기 때문에 continue 처리를 해준다.

next가 0이 아니라면 감염까지 남은 사람을 한명 빼준다.(temp가 감염되었기 때문에)

next에 해당하는 answer가 -1이고 (즉 감염되어 있지 않았던 상태) turn이 0이하 일 때(즉 next가 감염되지 않을 수 있는 주변인 감염수의 상한선보다 더 많은 주변인이 감염되었을 때) next가 감염된다. 이 때 큐에 next를 삽입해주고 answer[next-1]은 answer[temp-1]에 1을 더한 값이 된다.

 

코드

package Level3;

//bfs이용 

import java.util.*;
public class B19538_루머 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int N=7;
		int [][] a = { {0}, { 2,3,0 },{ 1,3,0 },{ 1,2,4,0 },{ 3,5,0 },{ 4,0 },{ 0 },{ 0 } };
		int M=2;
		int [] first_id= {1,6};
		int[] answer;
		answer=solution(N, a, M, first_id);
		
		for(int i=0;i<answer.length;i++) {
			System.out.print(answer[i]+" ");
		}
	}

	public static int[] solution(int N, int[][] adj, int M, int[] firstInfected) {
		int[] answer=new int[N];
		int[] turn=new int[N]; //몇명이상이 감염되어야 i번 사람이 감염되는지 -> turn[i]의 값이 0 이하일 때 감염
		
		Queue<Integer>q=new LinkedList<>();
		
		//answer 배열을 -1로 초기화 (처음 감염된 것인지 아닌지 구분하기 위함)
		for(int i=0;i<N;i++) {
			answer[i]=-1;
		}
		//최초생성자 처리 
		for(int t:firstInfected) {
			q.offer(t);
			answer[t-1]=0;
		}
		
		//몇명이상이 감염되어야 i번 사람이 감염되는지계산 
		for(int i=1;i<=N;i++) {
			turn[i-1]=adj[i].length/2;
		}
		
		while(!q.isEmpty()) {
			int temp=q.poll();
			
			for(Integer next : adj[temp]) {
				if(next==0)continue;
				
				//감염까지 남은 사람 빼줌 
				turn[next-1]-=1; //리턴배열은 0부터 사용하므로 1번 사람을 0번으로 저장하기 위해 인덱스 조정
				//answer[i]가 -1(새로 감염)이고 turn[i]가 0이하일 때
				if(answer[next-1]==-1&& turn[next-1]<=0) {
					q.offer(next);
					answer[next-1]=answer[temp-1]+1;
				}
			}
		}
		
		return answer;
	}
	
}