[백준 2606번 : 실버3] 바이러스 (DFS/Java)

이번 문제는 기초 DFS 문제였어서 금방 풀수가 있었다.

 

문제를 살펴보자.

 

문제

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

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

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

입력

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

출력

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

 

 

 

 

 

문제 접근 방법

 

이번 문제는 1번과 연결되어 있는 컴퓨터들만 확인해보면 되기때문에 DFS로 접근을 하였다.

DFS가 뭔지 모르는 분들은 아래 링크를 확인해보면 될것 같다.

https://wpioneer.tistory.com/130?category=1023663 

[자료구조] DFS(Depth First Search) Java 구현

 

 

너무 기초적인 DFS라서 따로 설명은 하지 않고 소스만 올리겠다.

 

import java.util.LinkedList;
import java.util.Scanner;

public class Run {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Run a = new Run();
		Scanner sc = new Scanner(System.in);
		
		int node = sc.nextInt(); //정점 개수
		int vertex = sc.nextInt(); // 간선 개수
		
		//연결 리스트를 담는 배열 선언 및 초기화 해주는 부분
		LinkedList<Integer>[] link = new LinkedList[node+1];
		
		for(int i = 0;i<=node;i++) {
			link[i] = new LinkedList<Integer>();
		}
		
		//연결리스트에 연결된 정점들 추가해주는 부분
		for(int i = 0; i<vertex;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			
			link[start].add(end);//시작정점에는 끝나는 정점을 추가
			link[end].add(start);//끝나는 정점에는 시작 정점 추가
		}
		
		boolean[] visit = new boolean[node+1];//방문 정점 체크하기 위해서 선언
		int answer = a.dfs(1,visit,link,0);
		System.out.println(answer);
	}

	public int dfs(int start, boolean[] visit, LinkedList<Integer>[] link, int count) {
		// TODO Auto-generated method stub
		visit[start] = true; //정점 방문 처리
		int length = link[start].size(); //정점과 인접노드 개수
		for(int i = 0;i<length;i++) {
			int node = link[start].get(i);
			if(!visit[node]) {//방문한적이 없으면 진입
				count++;
				count = dfs(node,visit,link,count);
			}
		}
		return count;
	}
}

 

 

 

느낀점

1. 연결 노드만 방문하고 끝내고 싶다면 DFS를 쓰는게 맞는것 같다.