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

문제 2606번

 : 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다
 : 네트워크 상에서 1번과 서로 연결되어 있는 컴퓨터들도 감염 (2번, 5번)
 : 감염된 컴퓨터들과 연결된 또 다른 컴퓨터들도 감염 (3번, 6번)

 

 [입력]

 :  첫째 줄에는 컴퓨터의 수 (컴퓨터의 수 100 이하인 양의 정수)

 :  둘째 줄에는 연결된 컴퓨터 쌍의 수
 :  셋째 줄부터 쌍을 이루는 컴퓨터 번호 나열

 

[출력]

 :  1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수 출력

 [DFS 코드]

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

public class Main {
	static int arr[][];
	static boolean visit[];

	static int N, M;
	static int result = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine()); 
		M = Integer.parseInt(br.readLine()); 

		visit = new boolean[N+1];
		arr	= new int[N+1][N+1];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			arr[x][y] = arr[y][x] = 1;
		}

		DFS(1);

		System.out.println(result);
	} 

	static void DFS(int node) {
		visit[node] = true;

		for(int i=1; i<N+1; i++) {

			if(arr[node][i] == 1 && visit[i] == false) {
				DFS(i);
				result++;
			}
		}

	} 
}

 

 [해설]
     

 :  static int arr[][];  2차원 배열 설정

    static boolean visit[];  방문기록 설정

    static int N, M;  첫째줄, 둘째줄 입력 설정

    static int result = 0;  결과값 0으로 초기화

 

:  N = Integer.parseInt(br.readLine());  컴퓨터의 수 입력받기

   M = Integer.parseInt(br.readLine());  컴퓨터 쌍의 수 입력받기

:  visit = new boolean[N+1];  배열이 0부터 시작하므로 1부터 시작하도록 계산하려면 +1 하기

   arr = new int[N+1][N+1];  배열 1부터 시작하게끔 + 1 하기

:  for(int i=0; i<M; i++) {  쌍을 이루는 개수만큼만 계산

         st = new StringTokenizer(br.readLine());  공백 단위로 단어 끊어 읽기

         int x = Integer.parseInt(st.nextToken());  연결 컴퓨터 1

         int y = Integer.parseInt(st.nextToken());  연결 컴퓨터 2

         arr[x][y] = arr[y][x] = 1;  arr[1][2] 과 arr[2][1] 은 같다는 표시
   }

:  DFS(1);  dfs에 1을 넣어서 호출

 

:  System.out.println(result);  결과 출력

:  static void DFS(int node) {  dfs 설정 / node = 컴퓨터 1
         visit[node] = true;  현재의 노드를 방문 처리 ( dfs(1)=true ) 기준을 잡는 것
         for(int i=1; i<N+1; i++) {  1부터 컴퓨터 개수 만큼 반복해서 찾아주기
                  if(arr[node][i] == 1 && visit[i] == false) {  node 컴퓨터와 연결됐지만 방문 기록이 false

                                                                                   arr[컴퓨터1][컴퓨터2]   /   visit[컴퓨터2]

                           DFS(i);                                             DFS(1)로 시작했으므로 컴퓨터1 = 1번 컴퓨터

                                                                                   즉 1번 컴퓨터와 연결됐지만 방문기록이 없다면 

                                                                                   다음번 DFS의 node를 현재의 [컴퓨터2]로 바꾸기

                           result++;  결과 +1 하기
                  }

         }

   }

      

이제 풀어보러 갈께요 :)

 

 

 

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *