[DFSBFS] 백준_2606_바이러스_DFSBFS_실버4

2021년 10월 14일 목요일 22시

 

[DFSBFS] 백준_2606_바이러스_DFSBFS_실버4

 

www.acmicpc.net/problem/2606

2606번: 바이러스

코드 1(인접행렬, DFS)

import java.util.Scanner;

public class Main {
	static int map[][];
	static boolean visit[];
	static int n, m, v;
	static int count = 0;
	
	public static int dfs(int i) {
		visit[i] = true;
		
		for(int j=1; j<=n; j++) {
			if(map[i][j] == 1 && visit[j] == false) {
				count ++;
				dfs(j);
			}
		}
		return count;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();	// 컴퓨터 수(정점)
		m = scan.nextInt();	// 연결된 컴퓨터 쌍의 수(간선)
		v = 1;	// 탐색 시장할 정점의 번호
		map = new int[n+1][n+1];	// 각 정점간 탐색 경로를 저장할 배열
		visit = new boolean[n+1];	// 정점의 탐색 여부 체크
		
		for(int i=0; i<m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			map[a][b] = map[b][a]= 1;
		}
		
		System.out.println(dfs(1));
		scan.close();
	}
}

 

코드 2(인접행렬, BFS)

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

public class Main {
	static int map[][];		// 각 정점간 탐색 경로 저장
	static boolean visit[];	// 정점 탐색여부 체크
	static int n, m, v;		// 정점, 간선, 시작 정점
	static int count = 0;	// 정점과 연결된 바이러스 걸리는 컴퓨터 수
	
	public static int bfs(int i) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(i);
		visit[i] = true;
		while(!q.isEmpty()) {
			int temp = q.poll();
			
			for(int k=1; k<=n; k++) {
				if(map[temp][k] == 1 && visit[k] == false) {
					q.offer(k);
					visit[k] = true;
					count ++;
				}
			}
		}
		
		return count;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();	// 컴퓨터 수(정점)
		m = scan.nextInt();	// 연결된 컴퓨터 쌍의 수(간선)
		v = 1;	// 탐색 시장할 정점의 번호
		map = new int[n+1][n+1];	// 각 정점간 탐색 경로를 저장할 배열
		visit = new boolean[n+1];	// 정점의 탐색 여부 체크
		
		// 인접행렬을 이용한 풀이
		for(int i=0; i<m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			map[a][b] = map[b][a]= 1;
		}
		
		System.out.println(bfs(1));
		scan.close();

	}

}

 

코드 3(인접리스트, DFS)

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static ArrayList<Integer>[] a;
	static boolean visit[];	// 정점 탐색여부 체크
	static int n, m, v;		// 정점, 간선, 시작 정점
	static int count = 0;	// 정점과 연결된 바이러스 걸리는 컴퓨터 수
	
	public static int dfs(int i) {
		visit[i] = true;
		for(int k : a[i]) {
			if(visit[k] == false) {
				count ++;
				dfs(k);
			}
		}
		return count;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();	// 컴퓨터 수(정점)
		m = scan.nextInt();	// 연결된 컴퓨터 쌍의 수(간선)
		v = 1;	// 탐색 시장할 정점의 번호
		a = new ArrayList[n+1];	// 인덱스 편의상 n+1설정, 0번째 요소는 사용 X
		visit = new boolean[n+1];
		for(int i=1; i<=n; i++) {
			a[i] = new ArrayList<Integer>();
		}
		
		for(int i=0; i<m; i++) {
			int u = scan.nextInt();	// 간선으로 이어진 정점1
			int v = scan.nextInt();	// 정점1과 간선으로 이어진 정점2
			a[u].add(v);
			a[v].add(u);
		}
		
		System.out.println(dfs(v));
		
		scan.close();
	}

}

인접리스트 DFS 설명 잘되있는곳

[Algorithm] DFS 깊이탐색

 

 

<참고>

https://zzang9ha.tistory.com/40

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