Java 백준 19538 루머

백준 링크

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

19538번: 루머

---

문제

입력

출력

입출력 예시

---

제출한 코드

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;

	static int n;
	static Node[] nodes;
	static Deque<int[]> q = new ArrayDeque<>();

	static class Node {
		boolean check;
		int time = -1;
		int cnt;
		List<Integer> link = new ArrayList<>();

		@Override
		public String toString() {
			return "Node [check=" + check + ", time=" + time + ", cnt=" + cnt + ", link=" + link + "]";
		}

	}

	public static void main(String[] args) throws Exception {
		init();
		run();
		printAnswer();
	}

	private static void init() throws Exception {
		n = Integer.parseInt(br.readLine());
		// 사람들을 저장할 Node 타입의 배열 할당
		nodes = new Node[n + 1];

		for (int i = 1; i <= n; i++) {
			// 초기 Node 생성
			nodes[i] = new Node();
			st = new StringTokenizer(br.readLine());

			// 0이 아닌 경우 까지 입력받아 link에 추가
			while (st.hasMoreTokens()) {
				int value = Integer.parseInt(st.nextToken());

				if (value == 0)
					break;

				nodes[i].link.add(value);
			}
		}

		// 최초 유포자
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			int value = Integer.parseInt(st.nextToken());
			// 최초 유포자의 값 수정 및 Queue에 데이터 삽입
			nodes[value].check = true;
			q.add(new int[] { value, 0 });
		}
	}

	private static void run() {
		// 루머가 퍼지는 로직
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int nowNum = cur[0];
			int nowTime = cur[1];
			// 루머를 믿기 시작한 시간 수정
			nodes[nowNum].time = nowTime;
			// 주변인들 루머 전파 시도
			for (int linked : nodes[nowNum].link) {
				// 이미 믿고 잇는 경우 연산X
				if (nodes[linked].check)
					continue;
				// 주변인들 중 루머를 믿는 사람 수 + 1
				nodes[linked].cnt++;

				// 주변인의 수
				int size = nodes[linked].link.size();
				// 짝수인 경우
				if (size % 2 == 0 && size / 2 > nodes[linked].cnt) continue;
				// 홀수인 경우
				else if (size % 2 != 0 && size / 2 + 1 > nodes[linked].cnt) continue;
				
				// 절반 이상 루머를 믿는 경우
				nodes[linked].check = true;
				q.add(new int[] { linked, nowTime + 1 });
			}

		}
	}

	private static void printAnswer() {
		StringBuilder sb = new StringBuilder();
		for (Node output : nodes) {
			if (output == null)
				continue;
			sb.append(output.time + " ");
		}
		System.out.print(sb);
	}
}

 

시간과 메모리 제한이 굉장히 여유롭게 주어진 문제였다.

 

주어지는 케이스의 범위가 굉장히 크다는 것을 유의해야한다.

 

루머를 퍼트린다고 해서 무조건 루머를 믿는게 아니라 주변인 절반 이상이 루머를 믿는 경우에만 루머를 믿는 것을 유의한다.

 

 

1. Node라는 객체 안에 모든 정보를 저장해서 문제를 해결했다.

2. 예제 입력에서 양방향 간선으로 데이터가 주어지니 따로 추가해 줄 필요는 없다.

3. 기본 루머가 퍼지는 로직은 run()안에서 이루어진다.

4. 처음 유포자를 입력 받으면서 방문처리 기능을 하는 Node 객체 안의 check값을 true로 변경해 주고 Queue에 삽입한다.

5. while문을 통해 Queue를 돌리면서 꺼내온 데이터의 time을 수정해준다.

6. 제일 먼저 cur과 양방향 간선을 이루고 잇는 node들의 cnt 값을 증가시킨다.

7. 증가된 cnt값이 해당 node의 link의 크기의 절반 이상인지 확인한다.

8. 절반을 넘는 경우에는 새롭게 Queue에 넣으면서 check 값을 true로 변경해 준다.

9. StringBuilder를 이용해서 20만 개 데이터 출력의 시간을 줄여준다.