728x90
[문제]
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
[문제 풀이]
이 문제는 BFS 또는 DFS를 이용하여 해결 할 수 있다.
그리고 BFS와 DFS를 구현하는데 matrix 또는 list로 구현이 가능한데 두 가지 방법으로 다 풀어보았다.
1. BFS Linked list
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 N, M;
static Queue<Integer> q = new LinkedList<>();
static boolean[] visited;
static Node[] adj;
static int stoi(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = stoi(br.readLine());
M = stoi(br.readLine());
visited = new boolean[N+1];
adj = new Node[N+1];
for (int i=0; i<M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = stoi(st.nextToken());
int v = stoi(st.nextToken());
adj[u] = new Node(v, adj[u]);
adj[v] = new Node(u, adj[v]);
}
System.out.println(bfs(1));
}
public static int bfs(int n) {
int cnt = 0;
visited[n] = true;
q.offer(n);
while(!q.isEmpty()) {
int x = q.poll();
for (Node node=adj[x]; node!=null; node=node.next) {
if (!visited[node.n]) {
q.offer(node.n);
visited[node.n] = true;
cnt++;
}
}
}
return cnt;
}
static class Node {
int n;
Node next;
public Node(int n, Node next) {
this.n = n;
this.next = next;
}
}
}2. DFS Linked list
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static Node[] adj;
static boolean[] visit;
static int cnt;
public static int stoi(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = stoi(br.readLine());
m = stoi(br.readLine());
adj = new Node[n+1];
visit = new boolean[n+1];
for (int i=0; i<m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = stoi(st.nextToken());
int v = stoi(st.nextToken());
adj[u] = new Node(v, adj[u]);
adj[v] = new Node(u, adj[v]);
}
dfs(1);
System.out.println(cnt);
}
public static void dfs(int v) {
visit[v] = true;
for (Node node=adj[v]; node!=null; node=node.next) {
if (!visit[node.n]) {
cnt++;
dfs(node.n);
}
}
}
static class Node {
int n;
Node next;
public Node(int n, Node next) {
this.n = n;
this.next = next;
}
}
}3. DFS Matrix
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static int[][] matrix;
static boolean[] visit;
static int cnt;
public static int stoi(String s) {
return Integer.parseInt(s);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = stoi(br.readLine());
m = stoi(br.readLine());
matrix = new int[n+1][n+1];
visit = new boolean[n+1];
for (int i=0; i<m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = stoi(st.nextToken());
int v = stoi(st.nextToken());
matrix[u][v] = 1;
matrix[v][u] = 1;
}
dfs(1);
System.out.println(cnt);
}
public static void dfs(int v) {
visit[v] = true;
for (int i=1; i<=n; i++) {
if (matrix[v][i]==1 && !visit[i]) {
cnt++;
dfs(i);
}
}
}
}[결과]
BFS - list
DFS - list
DFS - matrix
순으로 결과는 다음과 같이 나왔다.
728x90
'Algorithm > Baekjoon' 카테고리의 다른 글
| [BOJ] 1991 트리 순회 - Java (0) | 2021.07.16 |
|---|---|
| [BOJ] 5639 이진 검색 트리 - Java (0) | 2021.07.16 |
| [BOJ] 1068 트리 - Java (0) | 2021.07.14 |
| [BOJ] 11279 최대 힙 - Java (0) | 2021.07.14 |
| [BOJ] 1927 최소 힙 - Java (0) | 2021.07.14 |