[백준]_2606번 : 바이러스(파이썬 and C언어)

728x90

2606번: 바이러스

파이썬(dfs)

파이썬(bfs)

C언어(dfs)

 

bfs와 dfs 두 개의 방법으로 해결할 수 있는 문제이다.

파이썬(dfs)

문제 풀이의 기반이 되는 그래프를 먼저 그려야 한다. 여기서 말하는 그래프란 2차원 배열에 특정노드마다 어떤 노드들과 인접해 있는지 저장해 주는 그래프이다. 예를 들어 문제에서 예제로 제시된 <그림 1>을 보면 1 노드는 2 노드와 5 노드와 연결되어 있기 때문에 그래프에는 [ [ ], [ 2, 5 ] ...]와 같이 저장될 것이다. 저장하는 방법은 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input())
line = int(input())
graph = [[] for i in range(n + 1)]
for _ in range(line):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]

따라서 예제 입력에 의하면 그래프는 아래와 같은 형태를 띈다.

[[ ], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]

---

이제 dfs재귀 함수를 사용해서 1 노드와 연결된 노드들을 모두 visited에 표시해 줄 것이다.

visited = []
def dfs(node):
    visited.append(node)
    for el in graph[node]:
        if el not in visited:
            dfs(el)
    return 0
dfs(1)
print(len(visited) - 1)

마지막에 1을 뺀 이유는 1을 제외한 웜 바이러스에 걸린 컴퓨터들의 수를 반환해야 하기 때문이다.

최종 코드(Python, dfs)

import sys
input = sys.stdin.readline

n = int(input())
line = int(input())
graph = [[] for i in range(n + 1)]
for _ in range(line):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]

visited = []
def dfs(node):
    visited.append(node)
    for el in graph[node]:
        if el not in visited:
            dfs(el)
    return 0
dfs(1)
print(len(visited) - 1)

 

파이썬(bfs)

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
line = int(input())
graph = [[] for i in range(n + 1)]
for _ in range(line):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]
def bfs(node):
    visited = [0] * (n + 1)
    q=deque([node])
    while q:
        target=q.popleft()
        visited[target]=1
        for el in graph[target]:
            if visited[el]==0:
                visited[el]=1
                q.append(el)
    print(visited.count(1)-1)
bfs(1)

 

 

C언어(dfs)

#include <stdio.h>
int graph[100][100];
int visited[100];
int virus=0;
int n, line;
void dfs(int);
int main(){
    scanf("%d",&n);
    scanf("%d",&line);
    for (int i = 0; i < line; ++i) {
        int a,b;
        scanf("%d %d",&a,&b);
        graph[a-1][b-1]=1;
        graph[b-1][a-1]=1;
    }
    visited[0]=1;
    dfs(0);
    printf("%d",virus);
}
void dfs(int node){
    for (int i = 0; i < n; ++i) {
        if(visited[i]==0 && graph[node][i]==1){
            visited[i]=1;
            dfs(i);
            virus++;
        }
    }
}