[JAVA] 2606번 바이러스

문제링크

2606번: 바이러스

문제해석

 전형적인 탐색문제입니다. 1번 노드와 연결되어있는 노드의 개수가 몇개인지 파악하면 되므로, DFS 혹은 BFS로 탐색을 하여 연결된 노드를 탐색하면됩니다. 노드를 초기화 할 때는 양쪽 노드에 값을 추가해주어야

문제코드

1. DFS

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;

public class Main {

    public static boolean[] visited;
    public static ArrayList<ArrayList<Integer>> graph;

    public static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int num = Integer.parseInt(br.readLine());
        int edge = Integer.parseInt(br.readLine());
        visited = new boolean[num+1];
        graph = new ArrayList<>();

        for (int i = 0; i < num+1; i++) { // 노드 생성
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < edge; i++) { // 연결되어 있는 노드 초기화
            st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            int connectNode = Integer.parseInt(st.nextToken());
            graph.get(node).add(connectNode);
            graph.get(connectNode).add(node);
        }

        dfs(1);
        System.out.print(answer);

    }

    public static void dfs(int start) {
        visited[start] = true;
        ArrayList<Integer> nowNode = graph.get(start);
        for (int i = 0; i < nowNode.size(); i++) {
            if (visited[nowNode.get(i)] == false) { // 아직 방문하지 않았다면 방문하기
                answer++;
                dfs(nowNode.get(i));
            }
        }
    }

}

 

2. BFS

import java.sql.Array;
import java.util.*;
import java.io.*;

public class Main {

    public static boolean[] visited;
    public static ArrayList<ArrayList<Integer>> graph;
    public static ArrayDeque<ArrayList<Integer>> deque;

    public static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int num = Integer.parseInt(br.readLine());
        int edge = Integer.parseInt(br.readLine());
        visited = new boolean[num+1];
        graph = new ArrayList<>();
        deque = new ArrayDeque<>();

        for (int i = 0; i < num+1; i++) { // 노드 생성
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < edge; i++) { // 연결되어 있는 노드 초기화
            st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            int connectNode = Integer.parseInt(st.nextToken());
            graph.get(node).add(connectNode);
            graph.get(connectNode).add(node);
        }

        bfs(1);
        System.out.print(answer);

    }

    public static void bfs(int start) {
        visited[start] = true;
        deque.add(graph.get(start));
        while (deque.size() > 0) {
            ArrayList<Integer> nowNode = deque.poll();
            for (int i = 0; i < nowNode.size(); i++) {
                if (visited[nowNode.get(i)] == false) {
                    deque.add(graph.get(nowNode.get(i)));
                    visited[nowNode.get(i)] = true;
                    answer ++;
                }
            }
        }
    }

}