백준 2606번
바이러스
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
예제
알고리즘 분류
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
- 깊이 우선 탐색
코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int arr[][] = new int[N + 1][N + 1];
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int origin = Integer.parseInt(st.nextToken());
int destination = Integer.parseInt(st.nextToken());
arr[origin][destination] = arr[destination][origin] = 1; // 두 노드가 서로 연결되어 있다는 뜻
}
Queue<Integer> queue = new LinkedList<>();
boolean[] visit = new boolean[N + 1];
queue.add(1); // 1이 바이러스에 감염된 것을 베이스로 하기 때문
visit[1] = true; // 1이 바이러스에 감염된 것을 베이스로 하기 때문
int computer = 0;
while (!queue.isEmpty()) {
int temp = queue.poll();
for (int i = 1; i <= N; i++) {
if (arr[temp][i] == 1 && !visit[i]) {
visit[i] = true;
queue.add(i);
computer++;
}
}
}
System.out.println(computer);
}
}풀이
이 문제는 DFS(Depth-First Search, 깊이 우선 탐색), BFS(Breadth-First Search, 너비 우선 탐색) 두 가지 모두 사용 할 수 있다.
두 가지 모두 그래프를 탐색하는 방법이다.
그래프는 정점(node)와 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조이다.
그래서 이 그래프를 탐색한다는 것은 첫 정점에서 부터 순서대로 모든 정점들을 탐색하는 방식이다.DFS
루트 노드에서 시작해서 다음 갈래로 넘어가기 전에 해당 갈래를 모두 다 완벽하게 탐색하고 넘어가는 방식
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
- DFS가 BFS보다 좀 더 간단함
- 검색 속도 자체는 BFS에 비해서 느림
BFS
루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택
- 그래프의 모든 정점을 방문하는 것이 주요한 문제, 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없음
- 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
- 최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리
깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.
- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
츨처 : https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90
- 그 중 BFS를 활용하여 위 문제를 해결했다.
