[알고리즘 / 백준] 2606 - 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

 

문제는 위와 같으며, 이 문제는 BFS 를 구현할 수 있다면 쉽게 해결할 수 있는 문제입니다. 주어진 컴퓨터들의 연결 관계를 dictionary (자바에서는 Map) 형태로 구성한 뒤 BFS 탐색을 통해 방문할 수 있는 모든 컴퓨터의 수를 구한 뒤, -1 해주면 정답이 됩니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin


def bfs(node_list, start):
    need_visit = list()
    visited = list()

    need_visit.append(start)
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            if node in node_list:
                need_visit.extend(node_list[node])

    return len(visited) - 1


n = int(stdin.readline())
v = int(stdin.readline())

nodes = dict()
for _ in range(v):
    a, b = map(int, stdin.readline().split())

    if a in nodes:
        nodes[a].append(b)
    else:
        nodes[a] = [b]

    if b in nodes:
        nodes[b].append(a)
    else:
        nodes[b] = [a]

print(bfs(nodes, 1))

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int v = Integer.parseInt(br.readLine());
        Map<Integer, ArrayList> nodes = new HashMap<>();
        for (int i = 0; i < v; i++) {
            int[] ab = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            if (nodes.containsKey(ab[0])) {
                nodes.get(ab[0]).add(ab[1]);
            } else {
                nodes.put(ab[0], new ArrayList(Arrays.asList(ab[1])));
            }

            if (nodes.containsKey(ab[1])) {
                nodes.get(ab[1]).add(ab[0]);
            } else {
                nodes.put(ab[1], new ArrayList(Arrays.asList(ab[0])));
            }
        }

        System.out.println(bfs(nodes, 1));
    }

    private static int bfs(Map<Integer, ArrayList> node_list, int start) {
        ArrayList<Integer> need_visit = new ArrayList<>();
        ArrayList<Integer> visited = new ArrayList<>();

        need_visit.add(start);
        while (!need_visit.isEmpty()) {
            int node = need_visit.remove(0);
            if (!visited.contains(node)) {
                visited.add(node);
                if (node_list.containsKey(node)) {
                    need_visit.addAll(node_list.get(node));
                }
            }
        }

        return visited.size() - 1;
    }
}