[백준,BOJ 2606] 바이러스(JAVA 구현,추가풀이)

 

-내 생각

  단계별로 풀어보기 DFS, BFS로 분류되어 있는 백준 2606 바이러스 문제이다. 이전 단계에 백트래킹 알고리즘 단계가 있었는데 일반적으로 백트래킹의 경우 DFS를 기반으로 푼다는 글을 보고 우선 DFS와 BFS를 먼저 공부하기로 마음먹고 만난 문제다.(물론 이전에 DFS와 BFS 문제가 있었지만 단순한 개념 수준의 문제) 문제를 이해하는데 어려움은 없었고, 해법으로 처음 생각한 것은 단순히 인접 행렬로 그래프를 구성 후, 완전 탐색 방식인 DFS 또는 BFS를 사용하면 될 것 같았다. 그렇다면 DFS와 BFS 중 무엇을 사용해야 할지 선택해야 했는데, 문제 상으로는 바이러스에 감염된 컴퓨터와 인접한 컴퓨터부터 차례대로 감염된다는 언급이 있었기 때문에 한 노드의 인접한 노드를 모두 방문하는 BFS 알고리즘을 사용하기로 했다.

 

-해법

  문제에서 주어진 상황에 맞게 그래프를 구성한 이후 BFS메서드를 구현 해 감염될 때마다 카운트를 증가시켰다. 크게 어렵지 않았던 문제이므로 코드를 보면서 알아보자.

 

import java.util.*;



public class Main {
	static int node[][]; // 그래프 배열
	static int check[]; // 방문 배열
	static void bfs(int start) { // BFS 메소드
		Queue<Integer> queue = new LinkedList<>();
		
		check[start] =1;
		queue.offer(start);
		int cnt = 0; // 감염 된 컴퓨터의 수
		while(!queue.isEmpty()) {
			int x = queue.poll();
			
			for(int i=1;i<node.length;i++) { // 차례대로 1번과 연결 된 컴퓨터들을 찾아 cnt변수 증가 
				if(node[x][i]==1 && check[i]!=1) {
					queue.offer(i);
					check[i] = 1;
					cnt++;
				}
			}
		}
		System.out.println(cnt); //모든 탐색을 마치고 cnt 출력
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		
		int n= sc.nextInt(); // 컴퓨터의 수
		int m = sc.nextInt(); // 네트워크 상에 연결되어 있는 컴퓨터 쌍의 수 즉, 간선의 수
		
		node=new int[n+1][n+1];
		check = new int[n+1];
		for(int i=0;i<m;i++) { // 그래프 구성
			int a=sc.nextInt();
			int b = sc.nextInt();
			node[a][b]=1;
			node[b][a]=1;
			
		}
		
		bfs(1);
		
		
	}
	
}

---

  다시 만난 문제이다. BFS와 DFS의 차이는 사실 상 두 방법 모두 그래프에 대한 완전 탐색 방법이라 이전에 BFS만으로 풀었던 것과 다르게 DFS를 이용해도 충분히 해결이 가능한 문제였다. 여기서 짚고 넘어가고 싶은 것은 DFS는 모든 경우의 수를 탐색하고자 하는 미로 문제 같은 경우의 적합하고 BFS는 두 지점 사이의 최단 경로를 찾는 문제에 적합하다는 것이다. 그 이유는 미로 문제는 최단 경로가 아닌 탈출하는 경로를 고려하기 때문에 DFS와 같은 방식이 좋고, BFS를 사용하는 최단경로 문제는 DFS를 통해 하나의 경우로 깊이 탐색할 경우 가까운 최단경로를 두고 제대로 찾지 못할 수 있기 때문에 위와 같은 사용법이 있다고 생각한다. 

 

import java.util.Scanner;

class Main {
  	static int cnt = 0; // 감염시킨 컴퓨터 수
  	
    // DFS 메소드
	static void dfs(int[][] a, boolean[] check, int v) {
		if(check[v]==true) return; // 재귀호출 종료 부
		
		check[v] = true; // 방문처리 후
		cnt++; // 감염된 컴퓨터 수 증가, 여기엔 최초 방문 1번 컴퓨터도 포함된다.
		
		for(int i=0;i<a[v].length;i++) { // 인접행렬을 탐색
			if(a[v][i]==1 && !check[i]) // 연결된 정점이면서 방문하지 않은 경우
				dfs(a,check,i); // DFS 수행
		}				
	}
    
	public static void main(String[] args)  {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt(); // 정점의 수
		int e = in.nextInt(); // 간선의 수
		
		int a[][] = new int[n+1][n+1]; // 그래프를 인접행렬로 표시
		boolean check[] = new boolean[n+1]; // 정점 방문 여부 배열
		
		for(int i=0;i<e;i++) { // 인접행렬을 통한 연결정보 저장
			int v1 = in.nextInt();
			int v2 = in.nextInt();
			
			a[v1][v2] = 1;
			a[v2][v1] = 1;
		}
			
		dfs(a,check,1); // DFS 수행
		
		System.out.println(cnt-1); // 1번 컴퓨터는 제외해야 하므로 -1을 해준다.
	   
	  }
}

  해결 !