[백준] #2607. 바이러스 (Python)

작성일시: 2023년 7월 21일 오후 12:49

알고리즘 스터디에서 bobmyeonsoo가 준비한 문제!
난이도는 실버3이다.

📖Problems: #2606. 바이러스

신종 바이러스가 네트워크로 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에 연결되어 있는 모든 컴퓨터는 바이러스에 걸린다. 
어느날 1번 컴퓨터가 신종 웜 바이러스에 걸렸으며, 컴퓨터의 수와 네트워크 상에 서로 연결되어 있는 정보가 주어질 때, 
1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하라.

예시) 7대가 있을 때, 1번 컴퓨터가 웜 바이러스에 걸린다고 해보자.
1번과 연결된 2, 5번, 그리고 3번과 6번까지 2,3,5,6 네 대의 컴퓨터가 바이러스에 걸린다.

입력

7 # 컴퓨터의 수, 100이하의 양의 정수
6 # 네트워크 상의 컴퓨터 쌍의 수
1 2 # 여기서부터는 연결되어 있는 컴퓨터번호
2 3
1 5
5 2
5 6
4 7

출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수 출력

4

요약
1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하라.

 

🔍Institution

어떤 문제 유형일까? 그래프
→ 그래프 알고리즘에는 DFS, BFS가 있다.

• DFS → 스택, 재귀함수로 풀기
• BFS → 큐

이 문제 유형은 DFS로 하든, BFS로 하든 상관없지만 나는 하나의 노드와 연결된 게 없을 때까지 찾아야 한다고 생각하여 BFS 방식을 택하였다. 그 중에서도 재귀함수를 이용하였다.

 

🔍Procedure

1) 그래프 만들기

total_computer = int(input())
total_pairs = int(input())
graph = {}
for i in range(total_pairs):
    a, b = map(int, input().split())

    if a not in graph:
        graph[a]=[b]
    else:
        graph[a].append(b)

    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)

print(graph)

결과

7
6
1 2
2 3
1 5
5 2
5 6
4 7
{1: [2, 5], 2: [1, 3, 5], 3: [2], 5: [1, 2, 6], 6: [5], 4: [7], 7: [4]}

• 입력조건에 따라 1줄은 컴퓨터의 수를 입력받고,
• 2번째 줄은 컴퓨터 쌍의 수를 입력받는다.
• 이후, 컴퓨터 쌍의 수 만큼 반복하여, 2개의 값을 입력받는다.
  • 이때 그래프는 딕셔너리로 구성한다.
  • 또한 value 값은 연결된 것이 아니라 가장 마지막 값만 나오지 않도록 리스트 형태로 구성한다.
  • 리스트로 구성한 후,
  • 이미 value값이 존재하면, append할 수 있도록 조건문을 설정한다.
  • 밑에 graph[a] 뿐 아니라 graph[b] 에 대해서도 조건을 넣어주어 모든 노드에 대한 그래프 연결이 되도록 한다.

 

2) 탐색!

• 초기화
  • 노드를 방문하기 전에는 False, 방문하면 True로 설정하고 이를 visited리스트에 저장한다.
  • 컴퓨터의 개수를 구하는 것이므로 count 변수를 0으로 초기화한다.
  • start는 재귀할 때 시작하는 시작 노드를 의미하며, 1번부터 시작하므로 1로 초기화한다.
• 재귀함수
  • 방문한 노드에 대해 visited[start-1]값을 True로 바꿔준다. 이때, 방문노드는 1번부터 시작이지만 인덱스는 0부터 시작이므로 start-1로 설정한다.
  • 이후 해당 노드의 value에 해당하는 값만큼 반복하여 방문노드가 있는지 없는지 살핀다.
    • 만약에 방문하지 않아서 visited[i-1]값이 False라면,
    • 바이러스에 감염되었으므로 count += 1
    • 해당 노드 (i) 를 다시 재귀호출
• 최종적으로 count를 출력

아래는 작성한 코드이다. (최종 완성 아님)

visited = [False] * total_computer
start = 1
count = 0

def recursive(start):
    global count
    visited[start-1] = True
    for i in graph[start]:
        if visited[i-1] == False:
             count += 1
             recursive(i)

recursive(1)
print(count)

→ 키 에러가 발생했다! 키 에러는 딕셔너리에서 발생한다는 뜻이다. 키 값을 만드는 그래프가 아니라 키 값을 가지고 조회할 때, 문제가 발생한다는 것 →즉, recursive함수 내에서 발생했다는 뜻

key error가 나는 상황을 생각해보면, “그래프가 문제가 아니고, 그래프가 아예 연결이 안 된 상황에 대한 에러가 발생”한거다. (진짜 모르겠어서 JB가 힌트줌..)

if start in graph 라는 조건이 필요하다! (이거를 왜 생각을 못했찌……ㅜㅇㅜ)

아래는 최종 코드이다.

3) 최종 코드

# 그래프 만들기
total_computer = int(input())
total_pairs = int(input())
graph = {}
for i in range(total_pairs):
    a, b = map(int, input().split())

    if a not in graph:
        graph[a] = [b]
    else:
        graph[a].append(b)
    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)

# 탐색
visited = [False] * total_computer
start = 1
count = 0

def recursive(start):
    global count
    visited[start-1] = True
    if start in graph:
        for i in graph[start]:
            if visited[i-1] == False:
                count += 1
                recursive(i)

recursive(start)
print(count)

 

🚩My submission

최종 코드

# 그래프 만들기
total_computer = int(input())
total_pairs = int(input())
graph = {}
for i in range(total_pairs):
    a, b = map(int, input().split())

    if a not in graph:
        graph[a] = [b]
    else:
        graph[a].append(b)
    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)

# 탐색
visited = [False] * total_computer
start = 1
count = 0

def recursive(start):
    global count
    visited[start-1] = True
    if start in graph:
        for i in graph[start]:
            if visited[i-1] == False:
                count += 1
                recursive(i)

recursive(start)
print(count)

🚩Others submission

꼼꼼히 잘 적은 블로그인 것 같아 가져와보았다. 
https://bio-info.tistory.com/152

BFS

from collections import deque
visited[1]=1 # 1번 컴퓨터부터 시작이니 방문 표시
Q=deque([1])
while Q:
    c=Q.popleft()
    for nx in graph[c]:
        if visited[nx]==0:
            Q.append(nx)
            visited[nx]=1
print(sum(visited)-1)

DFS

def dfs(v):
    visited[v]=1
    for nx in graph[v]:
        if visited[nx]==0:
            dfs(nx)
dfs(1)
print(sum(visited)-1)

 

💡TIL

• 문제를 풀이하는 데에서 아이디어가 잘 안 떠올랐고, 역시 내 약점은 그래프쪽이라는 것을 알게 되었다.
• 그래프를 만드는 것부터 헤매게 되었는데, 이번 기회에 잘 복습하게 된 것 같다.
• 그래프 유형을 많이 풀어봐야겠다. 그리고 코드는 생각보다 간단하니까 겁먹지 말고, 차근히 코드를 작성해보자.
• 내가 한 코드가 맞을 때는 핸드 트레이싱 해보자!
• 이 부분도 잘 이해하면, 다른 방법으로도 풀어보고 싶다.