[Python] 백준 2606

 

 

 

 

BFS또는 DFS를 사용하는 그래프 탐색 문제다.

 

 

먼저, 입력받은 데이터는 딕셔너리로 구현하였다.

네트워크는 양방향 그래프 이므로 아래 코드와 같이 딕셔너리에 두 번 입력해야 한다. 

 

 

그래프 구현

net = {}

for i in range(n):
    a, b = map(int, input().split())
    if a in net :
        net[a].append(b)
    else : 
        net[a] = [b]
    if b in net :
        net[b].append(a)
    else :
        net[b] = [a]

 

 

 

같은 네트워크 상에 있는 컴퓨터를 검색하는 알고리즘은 BFS를 사용했다.

visit에서 1을 빼면 1과 연결되어 있는 컴퓨터만 남게 되기 때문에 len(visit)-1을 결과로 출력했다.

 

 

전체코드

m = int(input())
n = int(input())

net = {}

for i in range(n):
    a, b = map(int, input().split())
    if a in net :
        net[a].append(b)
    else : 
        net[a] = [b]
    if b in net :
        net[b].append(a)
    else :
        net[b] = [a]
        
queue = [1]
visit = []

while queue :
    temp = queue.pop(0)
    if temp not in visit :
        visit.append(temp)
        queue.extend(net[temp])

print(len(visit)-1)