[백준] 2606번 바이러스 - 파이썬

 💡그래프 탐색에는 BFS가 더 좋다 

DFS : 경우의 수를 탐색하는 방법 

BFS : 노드와 노드의 관계를 탐색하는 방법 

DFS 와 BFS

---

https://www.acmicpc.net/problem/2606

2606번: 바이러스

---

 

sol) 1번 컴퓨터와 네트워크 상 연결되어있는 컴퓨터의 수 출력 

 

DFS 풀이 

 

1. 각 노드에서 연결된 컴퓨터 리스트 만들기 

#노드 수 
n = int(input())
#네트원크 상에서 직접 연결되어 있는 컴퓨터의 쌍의 수 
m = int(input()) 

graph = [[] for _ i in range(n+1)]

for i in range(m) :
	a,b = map(int,input().split())
    #만일 a가 b와 연결되어 있을 경우 b포함 
    graph[a].append(b)
    #만일 b가 a와 연결되어 있을 경우 a 포함
    graph[b].append(a)

각 노드에 연결된 컴퓨터를 그래프로 나타내기

 

2.  visited를 설정하여 방문 여부를 판단

visited = [0 for i in range(n+1)]

def recur(node) :
	
    #방문처리
    visited[node] = 1
    
    for nxt in graph[node]:
    	#만일 방문한 적이 있는 경우 넘김
   		if visited[node] == 1 :
    		continue
      	recur(nxt)
 
recur(1)

 

3. 1번 컴퓨터와 연결되어 있는 수 출력 

print(sum(visited)-1)

 

4. 전체풀이

#DFS

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

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

#graph[1] = []
#graph[2] = []

visited = [0 for _ in range(n+1)]
#visited[1] = 0 #방문하지 않았을 경우 
#visited[1] = 1 #방문했을 경우 


for _ in range(m) :
    a,b = map(int,input().split())
    #그래프 a는 b를 포함하고 있다 
    graph[a].append(b)
    #그래프 b는 a를 포함하고 있다
    graph[b].append(a)

def recur(node) :

    visited[node] = 1
    for nxt in graph[node] :
        if visited[nxt] == 1 :
            continue  
        recur(nxt)

recur(1)
print(sum(visited) - 1)

 

BFS 풀이 

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

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

for _ in range(m) :
    a,b = map(int,input().split())
    #그래프 a는 b를 포함하고 있다 
    graph[a].append(b)
    #그래프 b는 a를 포함하고 있다
    graph[b].append(a)


from collections import deque 

q = deque() 
q.append(1) 

while q > 0  : #q가 0이 된다면 멈춤 
	node = q.popleft()
    visited[node] = 1  #방문처리 
    
    for nxt in graph[node] :
    	if visited[nxt] == 1 :
        	continue
        q.append(nxt) 

print(visited)