✔문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
✔입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
✔출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
💖 문제 풀이
문제의 그림에 그래프가 그려져 있다. 그래프를 1 과 연결되어 있는 연결 요소를 찾아야한다. 이는 그래프를 탐색을 통해서 수행한다.
그래프는 연결 리스트로 구현을 하였다. 이를 구현하기 위해서 각 노드 struct 를 선언하였고 노드를 생성하는 new_node함수를 그렸다.
선분을 그리는 add_edge 함수를 구현하였다. 이때 주의할 점은 이 그래프가 무방향 그래프라는 점이다. 따라서 입력을 받을때 (1,2)를 입력 받았다면 1 노드 뒤에 2를 추가하고 2 노드 뒤에도 1을 추가해 주어야한다.
bfs_virus 함수는 bfs 탐색으로 그래프를 탐색하여 1과 연결된 노드를 탐색한다. bfs는 queue를 이용하며, 이는 헤더를 include 하여 구현하였다.
- 파이썬을 이용해서 코딩을 할때는 2차원 배열을 이용하여 구현하였다. 2차원 리스트를 이용해서 dfs를 이용하여 리스트를 탐색하며 구현하였다. 이 방법이 훨씬 간단하고 빠르게 풀렸다.
💖 C++ 코드
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct node {
int number;
struct node* next;
}node;
struct node* new_node(int num) {
struct node* n =(struct node* ) malloc(sizeof(struct node));
if (n != NULL) { //malloc 성공시에만
n->next = NULL;
n->number = num;
}
return n;
}
void add_edge(int v1, int v2, struct node* vertex_array) {
struct node* v2_node = new_node(v2);
struct node* ptr = (struct node*)malloc(sizeof(struct node));
if (vertex_array[v1].next == NULL) {
vertex_array[v1].next = v2_node;
}
else {
if (ptr != NULL) {
ptr->next = vertex_array[v1].next; // vertex[v1]의 next 연결 요소 할당
while (ptr->next->next != NULL)//ptr의 다음 요소가 없을 때까지 next
{
ptr->next = ptr->next->next;
}
ptr->next->next = v2_node;
}
}
}
void bfs_virus(int n, struct node* vertex) {
int infected = 0;
queue <int> q;
bool* visited = new bool[n+1];
for (int i = 0; i < n + 1; i++)
visited[i] = false;
struct node* ptr = (struct node*)malloc(sizeof(struct node));
q.push(1);
while (!q.empty() )
{
int value = q.front();;
ptr = vertex[value].next;
while (ptr !=NULL) //value와 연결되어 있는 요소 queue에 추가
{
if(visited[ptr->number]==false) //방문하지 않은 경우만 push
q.push(ptr->number);
ptr = ptr->next;
}
visited[value] = true;
q.pop();
}
for (int i = 2; i <= n; i++) {
if (visited[i] == true) infected++;
}
cout << infected;
}
int main() {
int n, m;
cin >> n;
cin >> m;
struct node* vertex = new struct node [n+1];
for (int i = 0; i <= n; i++) {
vertex[i].next = NULL;
vertex[i].number = i+1;
}
for (int i = 0; i < m; i++) {
int v1, v2;
cin >> v1 >> v2;
add_edge(v1, v2, vertex );
add_edge(v2, v1, vertex); //무방향 그래프이므로 각 노드에 따로 추가해줌
}
bfs_virus(n, vertex);
return 0;
}💖 파이썬 코드
def dfs (map, n):
infected = 0
visited = [0 for num in range(n+1)]
stack = []
stack.append(1)
while(stack):
#맨위 pop
top = stack.pop()
#stack에 추가
for i in range(1,n+1):
if(map[top][i]==1 and visited[i] == 0):
visited[i] = 1
stack.append(i)
infected += 1
print(infected-1)
def main():
n = int(input())
m = int(input())
map = [[0 for col in range(n+1)]for row in range(n+1) ]
for i in range(m):
vertex1, vertex2 =input().split()
vertex1 = int(vertex1)
vertex2 = int(vertex2)
map[vertex1][vertex2] = 1
map[vertex2][vertex1] = 1
dfs(map, n)
if __name__ == "__main__" :
main()