백준 2606번: 바이러스 (DFS,BFS)

1. 문제

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

 

2. 설명

DFS, BFS로 풀 수 있는 문제다.

인접행렬 사용해서 풀었음

저번에 작성했던 DFS, BFS 코드를 참고했다.

 

3-1. DFS 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int virus = 0;
	static void dfs(int v, int[][] link, boolean[] visited) {
		if(visited[v]) return; // 방문했으면 return
		
		visited[v] = true;
		for(int i=0; i<link.length; i++) {
			if(!visited[i] && link[v][i]==1) {
				virus++;
				dfs(i, link, visited);
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 한 줄 입력
		int comp = Integer.parseInt(br.readLine()); // 컴퓨터 수
		int network = Integer.parseInt(br.readLine()); // 네트워크 수 
		
		StringTokenizer str; // 토큰단위 파싱
		int[][] link = new int[comp+1][comp+1]; // 인접행렬로 선언, 연결 링크
		
		for(int i=0; i<network; i++) {
			str = new StringTokenizer(br.readLine()); // 계속 입력받음
			int c1 = Integer.parseInt(str.nextToken());
			int c2 = Integer.parseInt(str.nextToken());
			
			link[c1][c2] = link[c2][c1] = 1;
		}
		br.close(); // bufferedreader 닫아주기
		
		boolean[] visited = new boolean[comp+1]; // 방문 여부
		
		dfs(1, link, visited); // dfs 시작
		System.out.println(virus);
	}
}

 

3-2. BFS 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int bfs(int v, int[][] link, boolean[] visited) {
		int virus = 0;
		Queue<Integer> q = new LinkedList<Integer>(); // 큐 선언
		visited[v] = true;
		q.add(v);
		
		while(!q.isEmpty()) {
			int x = q.poll(); // queue에서 하나 가꼬옴
			for(int i=1; i<link.length; i++) { // 탐색 실행
				if(!visited[i] && link[x][i]==1) {
					visited[i] = true;
					q.add(i);
					virus++; // 바이러스 수 증가
				}
			}
		}
		return virus;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 한 줄 입력
		int comp = Integer.parseInt(br.readLine()); // 컴퓨터 수
		int network = Integer.parseInt(br.readLine()); // 네트워크 수 
		
		StringTokenizer str; // 토큰단위 파싱
		int[][] link = new int[comp+1][comp+1]; // 인접행렬로 선언, 연결 링크
		
		for(int i=0; i<network; i++) {
			str = new StringTokenizer(br.readLine()); // 계속 입력받음
			int c1 = Integer.parseInt(str.nextToken());
			int c2 = Integer.parseInt(str.nextToken());
			
			link[c1][c2] = link[c2][c1] = 1;
		}
		br.close(); // bufferedreader 닫아주기
		
		boolean[] visited = new boolean[comp+1]; // 방문 여부
		
		System.out.println(bfs(1, link, visited)); // bfs 시작 및 출력
	}
}