[BOJ] 2606번 바이러스 / 사용언어 : 파이썬(python)

※ 문제링크

2606번: 바이러스

해당문제는 DFS 또는 BFS로 해결할 수 있는 문제였다. 두가지방법 모두 사용하는 방법을 숙달하기 위해서 두가지 방법을 모두 이용해서 코드를 작성해보았고, 그래프는 딕셔너리를 이용하여 구현하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력값을 반복문과 딕셔너리를 활용하여 그래프 형태로 변환한다.

2. dfs와 bfs함수를 작성하여 연결되어 있는 노드의 개수를 확인하고 결과값을 출력한다.

+ 처음에 작성한 코드는 dfs는 통과가 되었으나 bfs가 메모리초과가 나타나는 것으로 확인했다. 그래서 bfs만 따로 수정을 해주었고, 정상적으로 출력 및 통과가 되는 것으로 확인하였다.

 

N = int(input())
T = int(input())
graph = dict()
for _ in range(T):
    key, value = map(int, input().split())
    if key in graph:
        graph[key].append(value)
    else:
        graph[key] = [value]
    if value in graph:
        graph[value].append(key)
    else:
        graph[value] = [key]

# dfs
visited = [1]
def dfs(key):
    for line in graph[key]:
        if line in visited:
            continue
        visited.append(line)
        dfs(line)
dfs(1)
print(len(visited)-1)

# bfs
from collections import deque
def bfs(graph, start):
    visit = []
    queue = deque([])
    queue.append(start)

    while queue:
        node = queue.popleft()
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
    return visit
print(len(bfs(graph, 1)) -1)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.