[백준] 2606번 바이러스

사용 언어 - Python3

문제 -  2606번 바이러스

DFS (Depth-Frist search, 깊이 우선 탐색) = 경우의 수를 탐색하는 방법. 백트래킹 이용

BFS (Breadth-Frist search, 넓이 우선 탐색) = 노드와 노드의 관계를 탐색하는 방법. 그래프 탐색에 더 좋다.

 

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

2606번: 바이러스

 

 

정답

DFS / BFS 알고리즘을 활용해 그래프 탐색하기

0. 그래프 형태로 입력받기

각 노드에서 연결된 노드번호들 입력해준다.
graph[1] = [2,5]
graph[2] = [1,3,5]

 

1. 역주행 방지를 위해 방문 여부 확인

노드 2 방문 -> graph[2] = [1,3,5] 노드1 또 방문해주면 안된다. 불필요함

visited[1] = 1 방문처리

if visited[nxt] == 1: cotitnue 방문했다면, 무시하고 다음 노드3,5 방문해주기

 

2. output

방문한 친구들 합 = 노드 1,2,4,5,6 방문했으므로 5

정답은 노드1은 빼고 출력

print(sum(visited)-1)

 

 

DFS (재귀함수)

recur(1) 노드1부터 시작해서 모든 노드 방문해주기

노드1 방문 ->  graph[1] = [2,5] 2랑 5 방문해주기 recur(2), recur(5)

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())
    graph[a].append(b) # a -> b 연결
    graph[b].append(a) # b -> 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 (deque())

from collections import deque

q = deque()
q.popleft() / q.appendleft() 왼쪽부터 삭제가 가능한 자료구조 데큐(덱)

왼쪽부터 없애면 나랑 가까운 순서부터 탐색 가능하기 때문에 데큐 활용한다.

 

q.append(1) 첫번째 노드 방문

q가 있을 때까지 반복

node = q.popleft() 왼쪽부터 빼주면서 방문처리

graph[node] 방문안된 연결되어있는 노드들 한 개씩 방문해주면서 q에 추가해주기

q.append(nxt)

from collections import deque

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

for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

q = deque()
q.append(1)
while q:
    node = q.popleft()
    visited[node] = 1
    for nxt in graph[node]:
        if visited[nxt] == 0:
            q.append(nxt)
        
print(sum(visited)-1)

 

 

 

레퍼런스

• 깃허브 정답

DFS

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/2606_%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4.py

 

BFS

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/2606_%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A41.py

 

 

• DFS VS BFS

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

DFS, BFS의 설명, 차이점