Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

24. DFS와 BFS

그래프를 순회하는 알고리즘을 배워 봅시다.

Java / Python

2. 바이러스

2606번

BFS나 DFS로 그래프를 순회해서 방문할 수 있는 정점을 찾는 문제

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

BFS(Breath-First Search) : 너비 우선 탐색

• 큐로 구현 (FIFO원칙으로 탐색)
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

DFS(Depth-First Search) : 깊이 우선 탐색

• 재귀나 스택으로 구현
• 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

DFS는 모든 경우의 수를 탐색하고자 하는 미로 문제 같은 경우의 적합하고, BFS는 두 지점 사이의 최단 경로를 찾는 문제에 적합하다고 합니다.
미로 문제는 최단 경로가 아닌, 탈출하는 경로를 고려하기 때문에 DFS와 같은 방식이 유리하고, 최단경로 문제는 DFS를 이용하면 하나의 경우로 깊이 탐색할 경우 가까운 최단경로를 두고 제대로 찾지 못할 수 있기 때문에 BFS가 더 유리하다고 보입니다. 그래도 일반적으로 모든 경우를 다 탐색해야 하는 경우는 DFS가 더 선호되는 것으로 알고 있습니다.

• Java

BFS 이용
문제에서 바이러스에 감염된 컴퓨터와 연결된 컴퓨터부터 감염된다는 표현을 보고, 한 노드의 인접한 노드를 모두 방문하는 BFS 알고리즘을 이용했습니다.

import java.io.*;
import java.util.*;

public class Main {
	static int[][] node;	
	static boolean[] check;
	static int N;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));      
		StringTokenizer st;  
        
		N = Integer.parseInt(br.readLine());	// 정점
		int E = Integer.parseInt(br.readLine());	// 간선      
        
		node = new int[N + 1][N + 1];	// 각 정점간 탐색 경로를 저장할 배열
		check = new boolean[N + 1];		// 정점 탐색 여부 체크
        
		// 노드 , 간선 값 초기화
		for(int i = 0; i < E; i++){
			st = new StringTokenizer(br.readLine()); 
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			node[s][e] = 1;
			node[e][s] = 1;
		}
        
		bw.write(bfs(1) + "\n");

		bw.flush();
		bw.close();
		br.close();
	}

	public static int bfs(int st){
        
		Queue<Integer> queue = new LinkedList<Integer>(); 	
		queue.offer(st);
		check[st] = true;
		int cnt = 0;
		
		while(!queue.isEmpty()) {		
			int temp = queue.poll();

			for(int i = 1; i <= N; i++) {
				if(!check[i] && node[temp][i] == 1) {
					queue.offer(i);
					check[i] = true;
					cnt++;
				}
			}
		}
		return cnt;
	}
}

• Python

파이썬으로는 DFS 이용하여 풀어보았습니다.

import sys
N = int(sys.stdin.readline())
E = int(sys.stdin.readline())
node = [[0]*(N+1) for _ in range(N+1)]
check = [0 for _ in range(N+1)]
result = []

def dfs(v):
    check[v] = 1
    for i in range(1,N+1):
        if check[i] == 0 and node[v][i] == 1:
            result.append(i)
            dfs(i)
    return len(result)

for i in range(E):
    s, e = map(int, sys.stdin.readline().split())
    node[s][e] = 1
    node[e][s] = 1
    
print(dfs(1))