[S3] 바이러스 : Java : 2606 - BFS

문제

2606번: 바이러스

 

---

 

 

 

 

 

 

접근 방법

1번 노드를 시작으로 그래프가 끊길 때까지 전체 탐색을 하면 되는 문제라서 BFS나 DFS 중 아무거나 써도 될 것 같았다.

그래서 잘 안써본 BFS로 구현해봤다!

 

 

알게된 점

큐를 구현할 때 LinkedList를 이용해도 된다. 

• add : 맨 뒤에 요소를 삽입한다.
• poll : 맨 앞(제일 먼저 삽입된 요소) 요소를 제거 후 반환 한다.

 

 

코드

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


public class Main {

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Graph graph = new Graph(n+1);
        int edgeCount = Integer.parseInt(br.readLine());

        for(int i=0; i< edgeCount; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.addEdge(v,w);

        }
        System.out.println(graph.BFS(1));
    }


}
class Graph{
    int v;
    LinkedList []  adj;

    Graph(int v){
        this.v = v;
        adj = new LinkedList[v];
        for(int i=0; i<v; i++){
            adj[i] = new LinkedList();
        }
    }

    void addEdge(int v, int w){
        if(!adj[v].contains(w))
            adj[v].add(w);
        if(!adj[w].contains(v))
            adj[w].add(v);
    }

    int BFS(int value){
        int count = 0;
        boolean [] visited = new boolean[v];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[value] = true;
        queue.add(value);

        while(!queue.isEmpty()){
            int s = queue.poll();
            Iterator<Integer> iterator = adj[s].iterator();
            while (iterator.hasNext()){
                int n = iterator.next();
                if(!visited[n]){
                    count++;
                    queue.add(n);
                    visited[n]= true;
                }
            }
        }
        return count;
    }
}