[백준 2606번] 바이러스

🎯 백준 - 2606. 바이러스

🤔 나의 풀이

📌 문제

- 백준 2606번 바이러스

📌 날짜

2020.02.12

📌 시도 횟수

1 try

💡 Code 1 : DFS로 풀기

from collections import defaultdict
from collections import deque

n = int(input())
k = int(input())
graph = defaultdict(list)
for i in range(k):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

def dfs(i):
    if i in path:
        return
    path.add(i)
    global cnt # 전역 변수를 지역 범위에서 사용하기 위함
    cnt += 1

    for w in graph[i]:
        dfs(w)

    return cnt - 1 # 처음에 1번 컴퓨터도 세어 주었으므로 1을 뺀다.
    
path = set()
cnt = 0
print(dfs(1))

💡 Code 2 : BFS로 풀기

from collections import defaultdict
from collections import deque


def bfs(i):
    visited = set([i])
    queue = deque([i])
    count = 0

    while queue:
        count += 1
        next = queue.popleft()
        for x in graph[next]:
            if x not in visited:
                queue.append(x)
                visited.add(x)

    return count - 1 # 처음에 1번 컴퓨터도 세어 주었으므로 1을 뺀다.


n = int(input())
k = int(input())
graph = defaultdict(list)
for i in range(k):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

print(bfs(1))

💡 문제 해결 방법

- 기본적인 DFS, BFS의 틀을 활용하여 구현한 코드이다.
- 양방향 그래프를 생성하여 DFS(또는 BFS)를 이용해 1번 컴퓨터와 이어져있는
컴퓨터의 개수를 count로 세주었다.

💡 새롭게 알게 된 점

>> UnboundLocalError: local variable 'cnt' referenced before assignment
😾 bfs를 이용한 풀이에서 이러한 오류가 떴다.

😾 찾아보니 이는 전역변수를 지역범위에서 사용했더니 생기는 오류라고 한다.
따라서 전역 변수를 지역 범위 (local scope)에서 사용하고 싶으면 
지역 영역에서 global 표현을 사용해야 한다!

😾 따라서 BFS 풀이에서 cnt를 사용할때
>> global cnt  
>> cnt += 1 
와 같이 global 표현을 추가해주었다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

-