본문 바로가기

Programming/Python

[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)

 

 

 

 

 

'Programming > Python' 카테고리의 다른 글

[Python] 백준 2606  (0) 2020.09.01
[Python] 백준 1260  (0) 2020.08.27
[Python] 백준 2231  (0) 2020.05.03
[Python] 단일 치환 암호  (0) 2020.04.25
[Python] Ceasar cipher  (0) 2020.04.25