[JAVA] 바이러스 (백준 2606)

 

 

 

객체 배열로 한번 풀어봤다. 객체배열은 초기화를 따로 해줘야하는 것을 잊지말자...

 

bfs 로직은 심플하다. 

 

1. queue에 node가 있다면 node를 queue에서 꺼낸다. 없다면 종료한다.

2. node 의 방문여부를 체크하고 방문한 적 있다면 1번으로 간다.

3. 방문한적이 없다면 방문체크를 하고 answer를 1증가한다.

4. 나와 연결된 모든 node를 queue에 넣고 1번으로 간다.

 

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main{
    static int n,connectCnt;


    public static void main(String[] args) throws IOException{
        FastScanner fs = new FastScanner();
        n = fs.nextInt();
        int answer = 0;

        // object array
        Node[] nodes = new Node[n];
        for(int i=0;i<n;i++) nodes[i] = new Node();


        connectCnt = fs.nextInt();
        for(int i=0;i<connectCnt;i++){
            int[] input  = fs.readArray(2);
            nodes[input[0]-1].connected.add(nodes[input[1]-1]);
            nodes[input[1]-1].connected.add(nodes[input[0]-1]);
        }

//        Arrays.stream(nodes).forEach(System.out::println);
        Queue<Node> q = new LinkedList<>();
        q.offer(nodes[0]);

        while(!q.isEmpty()){
            Node cur = q.poll();

            if(cur.visited==1) continue;
            cur.visited = 1;
            answer++;

            for(Node node : cur.connected){
                q.offer(node);
            }
        }

        System.out.println(answer-1);


    }
    static class Node{
        int visited = 0;
        List<Node> connected = new ArrayList<>();


        public String toString(){
            return ""+connected.size();
        }
    }

    static class FastScanner{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public String next() throws IOException {
            while(!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException{
            return Integer.parseInt(next());
        }

        public int[] readArray(int n) throws IOException{
            int[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = nextInt();
            return a;
        }

    }
}