BOJ 19538 루머 C++, java, python (BFS 틀 잡기)

 

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

많이 어렵지 않은 bfs 문제이다.

이 문제로 bfs 문제의 틀을 잡는데 큰 도움을 받았다 !

 

[문제와 입출력]

루머는 최초 유포자로부터 시작한다. 최초 유포자는 여러 명일 수 있고, 최초 유포자를 제외하고 스스로 루머를 만들어 믿는 사람은 없다. 매분 루머를 믿는 사람은 모든 주변인에게 루머를 동시에 퍼트리며, 군중 속 사람은 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿는다. 루머를 믿는 순간부터 다른 말은 듣지 않기 때문에, 한번 믿은 루머는 계속 믿는다. 이때, 사람들이 루머를 처음 믿기 시작하는 시간을 알아내 보자.

 

 

입력을 간단히 설명하면

7명의 사람이 있다. (1 ≤ 사람 수 ≤ 200 000)

7개 줄에 걸쳐 각 번호의 사람과 연결된 사람을 입력받는데

각 줄에서의 0은 입력의 끝을 의미한다.

 

 

그 이후에 최초 유포자 수가 주어진다. (1 ≤ 최초 유포자 수 ≤ 전체 사람 수)

2명의 최초 유포자가 있는데

1번과 6번이다.

 

 

 

7명이 감염된 시간을 한 줄에서 공백 단위로 출력한다.

최초 유포자는 0분으로, 감염되지 않는 사람은 -1로 출력한다.

 

 

[알고리즘 설명: BFS]

BFS는 그래프를 탐색하는 기법 중 하나이다.

너비 우선 탐색(Breadth-First Search)은 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문한다.

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

 

BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)를 사용한다.

즉, 선입선출(FIFO) 원칙으로 탐색한다.

---

[문제 풀이 방법 설명]

bfs 문제의 전형적인 틀

예제 1번의 상황을 이어서 생각해보려 한다.

큐에는 감염된 사람의 번호가 들어갈 수 있다.

가장 처음에는 최초 감염자의 번호 1과 6을 큐에 넣는다.

큐에서 한 사람(1번)을 뺀다. 이 사람은 최초 감염자이므로 0분에 감염된 사람이다. 이 사람은 주변인에게 영향을 주었을 것이다. 감염된 사람의 모든 주변인들(2번과 3번)을 살펴보자!

 

2번과 3번 각각의 주변인 절반 이상이 감염되었는지 판별한 뒤 (판별은 조금 뒤에서 설명한다)

새로 감염되었다면

큐에 감염된 주변인 번호를 넣고

(2번이 감염되었으므로 2는 큐에 추가하지만 3번은 감염되지 않았으므로 큐에 추가되지 않는다)

큐에서 나온 사람(1)의 감염 시간(0분) + 1분을 해서 정답 배열을 갱신하면 된다.

 

이렇게 큐에 감염된 사람의 번호가 이어서 들어간다.

 

다시 큐에서 감염된 사람의 번호를 빼내어 주변인에게 끼치는 영향을 탐색한다.

아직 탐색하지 않는 최초 발견자(6번)가 주변인에게 어떤 영향을 끼치는지 탐색하고

1분에 감염된 사람(2번),

…

이렇게 이어서 탐색을 한다.

 

탐색을 하다가 큐가 빈다는 것은 더 이상 새로운 영향을 끼칠 사람이 없을만큼 감염이 충분히 이루어졌다는 뜻이다.

정답 배열 answer을 반환하면 알고리즘은 끝이다.

 

---

탐색 방법

이 문제는 “과연 주변인 절반 이상이 감염되었는지에 대해서는 어떻게 판별할 것인가?” 가 관건이다.

 

1. 몇 명 이상 감염되어야 i번 사람이 감염되는지를 구해 turn[i]에 저장한다.

 

주변인이 4명인 경우, 절반 이상인 2명 이상이 감염되어야 내가 감염된다.

주변인이 3명인 경우, 절반 이상인 2명 이상이 감염되어야 내가 감염된다.

 

몇 명 이상 감염되어야 하는지에 대한 수는 (주변인 수 + 1) / 2 연산의 몫으로 구할 수 있다.

 

2. bfs를 수행하면서 감염된 사람(큐에서 나온 사람)의 주변인의 감염까지 남은 주변인 수 (=turn[i])를 1씩 빼준다.

이렇게 하면 turn[i]의 값이 0과 같거나 0보다 작을 때, 감염되었음을 쉽게 판별할 수 있다.

 

3. 그런데 이미 감염된 사람을 새롭게 감염된 사람으로 판단하여 또 탐색하면 안된다. = 중복된 숫자가 큐에 들어가면 안된다.

 

예를 들어보자!

맨 먼저 1번이 감염되었을 때 2번은 감염되지만 3번은 주변인이 많아서 감염되지 않는다. 하지만 또다시 이미 감염된 1번을 중복해서 탐색하면 3번은 이를 인식하지 못하고 2명이 감염되었다고 인식 해 감염자 될 것이다.

 

이러한 중복을 방지하기 위해 answer 배열을 맨 처음에 -1로 초기화해두고,

answer[i]가 -1이고 turn[i]이 0과 같거나 0보다 작은 경우에 “새로” 감염됨을 판별하고 큐에 넣어야 할 것이다.

[C++ 소스코드]

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<int> solution(int N, vector<vector<int>> E, int M, vector<int> firstInfected) {
    queue<int> Q; // 감염된 사람의 번호를 큐에 저장할 것이다.
    vector<int> answer(N + 1, -1); // solution 함수에서 리턴할 배열, 사이즈 N+1, -1로 초기화
    vector<int> turn(N + 1, 0); // 감염까지 남은 주변 비감염 사람 수, 사이즈 N+1, 0로 초기화

    // 최조생성자 처리
    for (int t : firstInfected) {
        Q.push(t); // 최조생성자는 감염된 사람이고 주변인에게 영향을 주므로 큐에 넣어주고
        answer[t] = 0; // 0분에 감염되었음을 저장한다.
    }

    // 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿으므로
    // 몇 명이 감염되었을 때 자신이 감염되는지에 대한 정보를
    // 사람 i의 주변인물 수 + 1 / 2의 몫으로 저장해둔다.
    // 사람의 번호가 아닌 입력의 끝을 말하는 0이 adj 배열에 포함되어 있으므로 + 1은 안해도 된다.
    for (int i = 1; i <= N; i++)
        turn[i] = E[i].size() / 2;

    while (!Q.empty()) { // 큐가 빌 때까지 탐색하는데, 큐가 비었다면 모든 탐색을 마쳤다는 의미이다.
        int current = Q.front(); // 현재, 가장 먼저 감염된 사람의
        Q.pop();

        for (int next : E[current]) { // 주변인물들에게
            if (next == 0) break;
            turn[next] -= 1; // 자신(주변인물)이 감염되기까지 남은 사람 수를 1 빼고
            if (answer[next] == -1 && turn[next] <= 0) { // 만약 아직 감염되지 않았고 주변인의 반 이상이 감염되었다면
                Q.push(next); // 감염되었기에 큐에 자신의 번호를 넣어주고
                answer[next] = answer[current] + 1; // 자신을 감염시킨 마지막 주변인의 감염된 시간 + 1분을 더해 저장한다.
            }
        }
    }

    // 계산의 편의를 위해 배열에 0번 index가 아닌 1번 index부터 정답이 저장되었으므로,
    // 배열의 첫번째 원소를 지우고 반환한다.
    answer.erase(answer.begin());
    return answer;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> E(N + 1);
    for (int i = 1; i <= N; i++) {
        while (1) {
            int t;
            cin >> t;
            E[i].push_back(t);
            if (t == 0) break;
        }
    }

    int M;
    cin >> M;
    vector<int> firstInfected(M);
    for (int i = 0; i < M; i++) {
        int t;
        cin >> t;
        firstInfected.push_back(t);
    }

    vector<int> ans = solution(N, E, M, firstInfected);
    for (int i = 0; i < N; i++)
        cout << ans[i] << " ";
    cout << "\n";
}

[Python 소스코드]

import sys
from collections import deque


def solution(N, E, M, firstInfected):
    Q = deque([]) # 감염된 사람의 번호를 큐에 저장할 것이다.
    answer = [-1] * (N+1) # solution 함수에서 리턴할 배열, 사이즈 N+1, -1로 초기화
    turn = [0] * (N+1) # 감염까지 남은 주변 비감염 사람 수, 사이즈 N+1, 0로 초기화

    # 최조생성자 처리
    for t in firstInfected:
        Q.append(t) # 최조생성자는 감염된 사람이고 주변인에게 영향을 주므로 큐에 넣어주고
        answer[t] = 0 # 0분에 감염되었음을 저장한다.

    # 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿으므로
    # 몇 명이 감염되었을 때 자신이 감염되는지에 대한 정보를
    # 사람 i의 주변인물 수 + 1 / 2의 몫으로 저장해둔다.
    # 사람의 번호가 아닌 입력의 끝을 말하는 0이 adj 배열에 포함되어 있으므로 + 1은 안해도 된다.
    for i in range(1, N+1):
        turn[i] = (len(E[i])) // 2

    while Q: # 큐가 빌 때까지 탐색하는데, 큐가 비었다면 모든 탐색을 마쳤다는 의미이다.
        current = Q.popleft() # 현재, 가장 먼저 감염된 사람의
        for next in E[current]: # 주변인물들에게
            if next == 0:
                break
            turn[next] -= 1 # 자신(주변인물)이 감염되기까지 남은 사람 수를 1 빼고
            if answer[next] == -1 and turn[next] <= 0: # 만약 아직 감염되지 않았고 주변인의 반 이상이 감염되었다면
                Q.append(next) # 감염되었기에 큐에 자신의 번호를 넣어주고
                answer[next] = answer[current] + 1 # 자신을 감염시킨 마지막 주변인의 감염된 시간 + 1분을 더해 저장한다.
    
    # 계산의 편의를 위해 배열에 0번 index가 아닌 1번 index부터 정답이 저장되었으므로,
    # 배열의 두번째 원소부터 반환한다.
    return answer[1:] 


input = sys.stdin.readline
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(1, N+1):
    E[i] = list(map(int, input().split()))

M = int(input())
firstInfected = list(map(int, input().split()))
print(" ".join(map(str, solution(N, E, M, firstInfected))))

[JAVA 소스코드]

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

public class Main {

	public static int[] solution(int N, int[][] adj, int M, int[] firstInfected) {
		Queue<Integer> Q = new ArrayDeque<>(); // 감염된 사람의 번호를 큐에 저장할 것이다.
		int[] answer = new int[N + 1]; // solution 함수에서 리턴할 배열
		Arrays.fill(answer, -1); // 사이즈 N+1, -1로 초기화
		int[] turn = new int[N + 1]; // 감염까지 남은 주변 비감염 사람 수
		Arrays.fill(turn, 0); // 사이즈 N+1, 0로 초기화

		// 최조생성자 처리
		for (int t : firstInfected) {
			Q.add(t); // 최조생성자는 감염된 사람이고 주변인에게 영향을 주므로 큐에 넣어주고
			answer[t] = 0; // 0분에 감염되었음을 저장한다.
		}

		// 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿으므로
		// 몇 명이 감염되었을 때 자신이 감염되는지에 대한 정보를
		// 사람 i의 주변인물 수 + 1 / 2의 몫으로 저장해둔다.
		// 사람의 번호가 아닌 입력의 끝을 말하는 0이 adj 배열에 포함되어 있으므로 + 1은 안해도 된다.
		for (int i = 1; i <= N; i++)
			turn[i] = adj[i].length / 2;

		while (!Q.isEmpty()) { // 큐가 빌 때까지 탐색하는데, 큐가 비었다면 모든 탐색을 마쳤다는 의미이다.
			int current = Q.poll(); // 현재, 가장 먼저 감염된 사람의 

			for (Integer next : adj[current]) { // 주변인물들에게
				if (next == 0) break;
				turn[next] -= 1; // 자신(주변인물)이 감염되기까지 남은 사람 수를 1 빼고
				if (answer[next] == -1 && turn[next] <= 0) { // 만약 아직 감염되지 않았고 주변인의 반 이상이 감염되었다면
					Q.add(next); // 감염되었기에 큐에 자신의 번호를 넣어주고
					answer[next] = answer[current] + 1; // 자신을 감염시킨 마지막 주변인의 감염된 시간 + 1분을 더해 저장한다.
				}
			}
		}

		// 계산의 편의를 위해 배열에 0번 index가 아닌 1번 index부터 정답이 저장되었으므로,
		// 배열을 두번째 원소부터 잘라 반환한다.
		return Arrays.copyOfRange(answer, 1, answer.length);
	}
	
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		int[][] adj = new int[N+1][];
		adj[0] = new int[]{0};
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			List<Integer> arrayList = new ArrayList<>();
			while (true) {
				int temp = Integer.parseInt(st.nextToken());
				arrayList.add(temp);
				if (temp == 0) {
					adj[i] = arrayList.stream().mapToInt(Integer::intValue).toArray();
					break;
				}
			}
		}

		int M = Integer.parseInt(br.readLine());
		int[] firstInfected = new int[M];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int temp = Integer.parseInt(st.nextToken());
			firstInfected[i] = temp;
		}
		Arrays.stream(solution(N, adj, M, firstInfected)).forEach(t -> sb.append(t).append(" "));
		System.out.println(sb);
	}
}