[백준/BOJ] 2606번 : 바이러스 _Python

2606번: 바이러스

 

>문제

>접근방법

   그래프 탐색 dfs, bfs 사용하기

 

 

>풀이법

1) 깊이우선탐색(반복)[DFS]

   1. 2차원 리스트 생성 후 입력값 append

   2. dfs함수 - 스택을 이용한 깊이우선탐색 수행

   3. dfs의 리턴값 visit의 개수에서 1을 뺀 값 출력

 

2) 깊이우선탐색(재귀)[DFS]

   1. 2차원 리스트 생성 후 입력값 append

   2. dfs함수(재귀) - dfs함수를 재귀적으로 호출

   3. visit 대신 한 번 dfs를 수행할 때마다 count에 1을 더해준다.

   4. count 출력

 

3) 너비우선탐색[BFS]

   1. 2차원 리스트 생성 후 입력값 append

   2. 방문여부 확인 리스트를 false로 초기화

   3. 스택 대신 큐를 이용한다.

   4. 노드 방문 순서가 담긴 리스트 visit의 길이 출력

 

 

>코드

1) 깊이우선탐색 (반복)

n = int(input())
num = int(input())

virus = [[]*n for _ in range(n+1)]

for i in range(num):
    inNet, outNet = map(int, input().split())
    virus[inNet].append(outNet)
    virus[outNet].append(inNet)

def dfs(network, S):
    visit = list()
    stack = list()

    stack.append(S)

    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(network[node])
    return visit

print(len(dfs(virus, 1))-1)

 

2) 깊이우선탐색 (재귀)

n = int(input())
num = int(input())
count = 0

virus = [[]*n for _ in range(n+1)]
visited = [False for _ in range(n+1)]

for i in range(num):
    inNet, outNet = map(int, input().split())
    virus[inNet].append(outNet)
    virus[outNet].append(inNet)

def dfs(network, S, visited):
    global count
    visited[S] = True
    for i in network[S]:
        if visited[i] == False :
            count += 1
            dfs(network, i, visited)

dfs(virus, 1, visited)
print(count)

 

3) 너비우선탐색

from collections import deque

n = int(input())
num = int(input())

visited = [False for _ in range(n+1)]
virus = [[]*n for _ in range(n+1)]

for i in range(num):
    inNet, outNet = map(int, input().split())
    virus[inNet].append(outNet)
    virus[outNet].append(inNet)

def bfs(network, S, visited):
    queue = deque([S])
    visit = []
    visited[S] = True

    while queue:
        node = queue.popleft()
        for i in network[node]:
            if not (visited[i]):
                queue.append(i)
                visit.append(i)
                visited[i] = True
    return visit

print(len(bfs(virus, 1, visited)))

 

>결과

 

 

>결론 

그래프 어렵고 재밌다