[ Baekjoon - 10/29 ] - 2606번: 바이러스

• 문제 링크 : https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

• 소요 시간 : 15분

바이러스

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

114556

55077

37094

46.184%

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1 복사

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1 복사

4

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 128MB
   • 문제
     
     • 컴퓨터의 수 N(0≤N≤100), 네트워크로 연결된 컴퓨터의 관계 L(1≤L≤N)
     • 한 컴퓨터가 바이러스에 걸리면, 해당 컴퓨터와 같은 네트워크에 연결된 컴퓨터는 모두 감염된다면,
       1번 컴퓨터가 감염될때, 같이 감염되는 컴퓨터의 수를 출력하는 문제
   • 이해
     • 문제 그대로이다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 이해에 어려움은 없어서 생략
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 인접리스트와 BFS)
   • 컴퓨터의 네트워크 관계가 중요하므로, 연결관계를 바로 알수있는 인접리스트를 선택했고 BFS를 통해 같은 네트워크인지 판단하며 방문한 곳이 아니면 cnt+=1를 하며 구하면 된다.
4. 위 계획을 검증
   • 흔한 유형이므로 생략
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main{
            static int N,K,ans;
            static List<Integer>[] adjList;
            static boolean[] vis;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                N = Integer.parseInt(br.readLine());
                adjList = new ArrayList[N+1];
                for (int n = 1; n < N+1; n++) {
                    adjList[n] = new ArrayList<>();
                }
                vis = new boolean[N+1];
        
                K = Integer.parseInt(br.readLine());
                for (int k = 0; k < K; k++) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    int a = Integer.parseInt(st.nextToken());
                    int b = Integer.parseInt(st.nextToken());
                    // 양방향
                    adjList[a].add(b);
                    adjList[b].add(a);
                }
        
                BFS(1);
                System.out.println(ans-1);
            }
        
            private static void BFS(int idx) {
                Queue<Integer> q = new LinkedList<>();
                q.add(idx);
                while(!q.isEmpty()){
                    // 큐에서 꺼냄
                    int nIdx = q.poll();
                    // 목적지인가 - 필요없
                    // 연결되어있는가
                    for (int i = 0; i < adjList[nIdx].size(); i++) {
                        int node = adjList[nIdx].get(i);
                        // 갈수있는가
                        if(!vis[node]) {
                            // 체크인
                            vis[node] = true;
                            ans+=1;
                            //큐에 넣음
                            q.add(node);
                        }
                    }
                }
            }
        }

 

• 결과