[문제 풀이] 백준 2606번 바이러스 JAVA

문제

  문제접근 방법   

해당 문제는 신종 바이러스가 네트워크를 통해 전판 되다고 할 때 컴퓨터의 수와 각각 연결된 컴퓨터 상이 존재할 때 1번 컴퓨터가 바이러스에 걸리게 되면 바이러스에 걸리는 컴퓨터의 수를 구하는 프로그램을 작성하는 문제이다.

문제를 읽고 인접 리스트를 통해서 1과ㅏ 연결된 컴퓨어의 수를 카운틀해야겠다는 생각이 들어 아래와 같이 코드를 작성하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[];
    public static int count=0;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int computerN=s.nextInt();
        int linkedN=s.nextInt();
        visited=new boolean[computerN+1];
        List<ArrayList<Integer>> linkedComputer=new LinkedList<>();
        for(int i=0;i<=computerN;i++){
            linkedComputer.add(new ArrayList<>());
        }
        for(int i=0;i<linkedN;i++){
            int n1=s.nextInt();
            int n2=s.nextInt();
            linkedComputer.get(n1).add(n2);
            linkedComputer.get(n2).add(n1);
        }
        
        bfs(1,linkedComputer);
        System.out.print(count);
    }
    public static void bfs(int start,List<ArrayList<Integer>> linkedComputer){
        Queue<Integer> q=new LinkedList<>();
        q.offer(start);
        visited[start]=true;
        
        while(!q.isEmpty()){
            int num=q.poll();
            for(int i=0;i<linkedComputer.get(num).size();i++){
                if(!visited[linkedComputer.get(num).get(i)]){
                    visited[linkedComputer.get(num).get(i)]=true;
                    q.offer(linkedComputer.get(num).get(i));
                    count++;
                }
            }
        }
    }
}

인접 리스트에서처럼 List<ArrayList<Integer>> linkedComputer=new LinkedList <>();를 선언해 주고 해당 list에 각각의 컴퓨터 연결 쌍 입력받은 것을 저장해 준다, 이후 1과 연결된 컴퓨터, 연결된 컴퓨터와 연결된 컴퓨터 이 모든 컴퓨터들을  bfs를 통해 탐색하고 탐색할 때마다 count 해서 바이러스에 걸린 컴퓨터의 수를 구할 수 있었다.

 

  마무리  

해당 문제는 인접 리스트를 활용하여 문제를 접근할 수 있었고 인접리스트라는 것을 구현할 수 있고 생각할 수 있다면 

어렵지 않게 해결이 가능한 문제라고 생각된다.

 

  추가 코드 분석 및 풀이  

해당 문제도 BFS로 풀이했지만 DFS로도 풀이가 가능하다.

< 추가 코드 ver DFS >

- 추후 업데이트 예정

 

 

 참고 자료