[Python] 바이러스 - BFS

문제 2606

해당 문제 링크

정답

# 바이러스

from collections import deque

num=int(input())

edge = int(input())

matrix = [[0]*(num+1) for _ in range(num+1)] ##방문 체크할 리스트

visited=[0]*(num+1)

for _ in range(edge):
    a, b=map(int, input().split()) 
    matrix[a][b]=matrix[b][a]=1

def bfs(i):
    answer=0
    q=deque()
    q.append(i)

    visited[i]=1

    while q:
        x=q.popleft()
        for i in range(1, num+1):
                if not visited[i] and matrix[x][i]==1:
                    q.append(i)
                    answer+=1
                    visited[i]=1

    return answer

root_node=1
print(bfs(root_node))

또 다른 정답

from sys import stdin

n = int(stdin.readline())
v = int(stdin.readline())

graph = [ [] for _ in range(n+1) ]
visited = [0] * (n+1)

for i in range(v) : 
    a, b = map(int, stdin.readline().split())

    graph[a] += [b]
    graph[b] += [a]
    print(graph)

def dfs(k) : 
    visited[k] = 1

    for nx in graph[k] : 
        if visited[nx] == 0 : 
            dfs(nx)

dfs(1)
print(sum(visited)-1)

dfs를 이용하면서 아래와 같이 그래프를 만들어 답을 도출했다..
어떻게 이렇게 푸는 방법들을 아는 건지..간단하고 간결한 코드라고 생각한다.

풀이

이전 문제 DFS와 BFS 코드를 이용하여 풀었다. 이전 문제 코드를 잘 분석해서 풀어서 이번에는 어떻게 작성하면 나올지 감이 와서 해결했다.
첫번째 root_node를 지정해주면 1 컴퓨터와 연결되지 않은 노드는 나오지 않아 1과 연결되어 있는 노드만 세면 되는 문제였다. 더 간단한 답은 무엇이 있을까 알아보던 중 더 간단히 해결되는 답이 있어서 다른 풀이도 보며 학습하였다.