DFS(Depth-First Search) 즉 깊이 우선 탐색이라고 불린다.
Baekjoon 2606: 바이러스
DFS Solution
import sys
read = sys.stdin.readline
dic={}
for i in range(int(read())):
dic[i+1] = set()
for j in range(int(read())):
a, b = map(int,read().split())
dic[a].add(b)
dic[b].add(a)
def dfs(start, dic):
for i in dic[start]:
if i not in visited:
visited.append(i)
dfs(i, dic)
visited = []
dfs(1, dic)
print(len(visited)-1)
이 문제는 BFS함수를 이용해서도 풀 수 있다.
BFS Soultion
import sys
read = sys.stdin.readline
dic={}
for i in range(int(read())):
dic[i+1] = set()
for j in range(int(read())):
a, b = map(int,read().split())
dic[a].add(b)
dic[b].add(a)
def bfs(start, dic):
queue = [start]
while queue:
for i in dic[queue.pop()]:
if i not in visited:
visited.append(i)
queue.append(i)
visited = []
bfs(1, dic)
print(len(visited)-1)
억텐 없는 첫 포스팅은 좀 귀하네요..