BOJ - 바이러스

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

2606번: 바이러스

 

• 그래프 문제이다
• 1번에서 출발하여 연결된 모든 노드를 순회만 하면 되기때문에 DFS, BFS 둘다 풀어도 될 것같다.
• 코드는 BFS로 풀었다.
• 1번을 제외한 감염된 컴퓨터를 출력하면 된다.

 

 

import java.util.*;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws Exception {
        int N = scanner.nextInt();
        int C = scanner.nextInt();

        ArrayList<Integer>[] adj = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 1; i <= C; i++) {
            int s = scanner.nextInt();
            int r = scanner.nextInt();

            adj[s].add(r);
            adj[r].add(s);
        }

        boolean[] visited = new boolean[N + 1];
        Queue<State> queue = new LinkedList<>();
        queue.offer(new State(1, 1));
        while (!queue.isEmpty()) {
            State node = queue.poll();
            if (visited[node.currentNode] == true) continue;
            visited[node.currentNode] = true;

            for (int i = 0; i < adj[node.currentNode].size(); i++) {
                Integer next = adj[node.currentNode].get(i);
                if (visited[next] == true) continue;
                queue.offer(new State(next, node.depth + 1));
            }
        }
        int numOfVisited = 0;
        for (boolean visit : visited) {
            if (visit) numOfVisited++;
        }

        System.out.println(numOfVisited - 1);
    }
}

class State {
    public int currentNode;
    public int depth;

    public State(int currentNode, int depth) {
        this.currentNode = currentNode;
        this.depth = depth;
    }
}