[백준 2606번] 바이러스 - BFS, DFS

 

# BFS와 DFS 알고리즘을 공부한 뒤 바로 예제문제를 풀어보았다.

 

-- 처음 짠 코드

# bfs 방식

import sys
from collections import deque

n = int(input()) # 컴퓨터의 수
ssang = int(input()) # 연결되어 있는 컴퓨터 쌍의 수

network = {} # 네트워크를 저장할 딕셔너리

for i in range(ssang):
    a, b = map(int,sys.stdin.readline().split())
    network[a] = network.get(a,[]) # 시작 : 끝 순서로 딕셔너리를 완성!
    network[a].append(b)

for i in network.keys(): # bfs 알고리즘을 돌리기 위해 value type을 set으로 변경
    network[i] = set(network[i])

start = 1

def BFS_with_adj_list(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in network:
            visited.append(n)
            continue
        else:
            if n not in visited:
                visited.append(n)
                queue += graph[n] - set(visited)
    return visited

print(len(BFS_with_adj_list(network, start))-1)

예제가 옳게 나와 정답이 될 줄 알았는데 틀렸다는 결과가 나왔다. 흠........ 어디가 잘못됐는지 코드를 좀더 자세히 봐보자..

 

* 코드를 컴팩트하게 만들기 위해 

1. network 딕셔너리의 value값을 처음부터 set형태로 만든다.

2. queue를 만들 때 딕셔너리 value값을 get을 사용해 가져온다.

 

-- 정답 코드

 

import sys
from collections import deque

n = int(input()) # 컴퓨터의 수
ssang = int(input()) # 연결되어 있는 컴퓨터 쌍의 수

network = {} # 네트워크를 저장할 딕셔너리

for i in range(ssang):
    a, b = map(int,sys.stdin.readline().split())
    network[a] = network.get(a,set()) # 시작 : 끝 순서로 딕셔너리를 완성!
    network[b] = network.get(b,set())
    network[a].add(b)
    network[b].add(a)

start = 1

def BFS_with_adj_list(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in network:
            if n not in visited:
                visited.append(n)
            continue
        else:
            if n not in visited:
                visited.append(n)
                queue += graph.get(n,set()) - set(visited)
    return visited
print(len(BFS_with_adj_list(network, start))-1)

답이 틀린 가장 큰 이유는 입력된 경로를 한 방향으로만 입력했기 때문이다. 그걸 생각 못하고 queue 를 잘못만든 것이라 생각해 queue만 오류 수정을 1시간을 했더니 머리가 지끈지끈하다..

 

해결했으니 이제 괜찮다 ㅎㅎ

 

 

 

오늘도 성공적으로 전염된 바이러스를 찾아냈다.