BFS - 너비 우선 탐색 / DFS - 깊이 우선 탐색

너비 우선 탐색(Breadth First Search) / DFS(Depth First Search)은 시작지점부터 갈 수 있는 지점들을 들리면서, 더이상 갈 곳이 없을때까지 반복한 후 종료한다.

 

ex)

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

2606번: 바이러스

해당 문제는 이런 모양의 간선과 노드들로 이루어져 있습니다.

1번 컴퓨터에 바이러스가 걸리게 된다면, 1과 2, 3, 5, 6 총 4개의 컴퓨터가 1번 컴퓨터에 의해 바이러스에 감염되면서, 5개의 컴퓨터가 바이러스에 걸리게 됩니다.

 

해당 문제는 BFS / DFS(인접행렬, 인접리스트)로 풀 수 있습니다. 왠만해서는 DFS로 풀시, 인접리스트를 추천드립니다.

<인접 리스트 BFS>

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

public class Main {
	static ArrayList<Integer>[] arr;
	static boolean[] visited;
	static int n, answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		n = Integer.parseInt(br.readLine()) + 1;
		int m = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n]; // 인접 리스트
		visited = new boolean[n]; //방문 체크
		
		for(int i = 1; i < n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		while(m --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			
			arr[a].add(b);
			arr[b].add(a);
		}
		
		dfs(1); // 1번 컴퓨터 부터 시작
		
		System.out.print(answer - 1); // 1번 컴퓨터를 제외한 감염된 컴퓨터 개수
	}
	
	public static void dfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[n];
		visited[start] = true;
		queue.add(start);
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			
			answer++;
			
			for(int i = 0; i < arr[now].size(); i++) {
				int next = arr[now].get(i);
				
				if(!visited[next]) {
					visited[next] = true;
					queue.add(next);
				}
			}
		}
	}
}

<인접 행렬 DFS> 

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

public class Main {
	static int[][] arr;
	static boolean[] visited;
	static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int n = Integer.parseInt(br.readLine()) + 1, m = Integer.parseInt(br.readLine());
		
		arr = new int[n][n]; // 인접 행렬
		visited = new boolean[n]; //방문 체크
		
		while(m --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			
			arr[a][b] = 1;
			arr[b][a] = 1;
		}
		
		dfs(1); // 1번 컴퓨터 부터 시작
		
		System.out.print(answer - 1); // 1번 컴퓨터를 제외한 감염된 컴퓨터 개수
	}
	
	public static void dfs(int start) {
		if(start == arr.length) {
			return;
		} // 마지막 컴퓨터까지 확인 했으면 종료
		
		visited[start] = true;
		answer++;
		
		for(int i = 0; i < arr.length; i++) {
			if(arr[start][i] == 1 && !visited[i]) {
				dfs(i);
			} // 감염된 컴퓨터와 연결되어 있으면 전염
		}
	}
}

<인접 리스트 DFS>

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

public class Main {
	static ArrayList<Integer>[] arr;
	static boolean[] visited;
	static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int n = Integer.parseInt(br.readLine()) + 1, m = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n]; // 인접 리스트
		visited = new boolean[n]; //방문 체크
		
		for(int i = 1; i < n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		while(m --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			
			arr[a].add(b);
			arr[b].add(a);
		}
		
		dfs(1); // 1번 컴퓨터 부터 시작
		
		System.out.print(answer - 1); // 1번 컴퓨터를 제외한 감염된 컴퓨터 개수
	}
	
	public static void dfs(int start) {
		if(start == arr.length) {
			return;
		} // 마지막 컴퓨터까지 확인 했으면 종료
		
		visited[start] = true;
		answer++;
		
		for(int i = 0; i < arr[start].size(); i++) {
			if(!visited[arr[start].get(i)]) {
				dfs(arr[start].get(i));
			} // 감염된 컴퓨터와 연결되어 있으면 전염
		}
	}
}

 

 

 

※ BFS 관련 문제 추천

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

4963번: 섬의 개수

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

2667번: 단지번호붙이기