DFS / BFS

BFS(Breadth First Search) 너비 우선 탐색

• 시작 정점으로부터 가까운 정점을 방문하고, 멀리 떨어진 정점을 나중에 방문하는 순회방식
• 두 노드사이의 최단경루를 탐색하거나, 임의의 경로를 검색할 때 사용한다.
• 큐 자료구조를 사용한다.
• 데이터가 N개의 개수인 경우, O(N)의 시간이 소요된다.

while len(queue) > 0;
	count = len(queuq) # 같은 거리에 존재하는 큐 데이터 개수
    for time in range(count):
    	now = queue.pop(0)	# 같은 거리에 있는 큐 갯수만큼 검사
        if now == dest:		# 정답이 존재하면 반환
        	return answer
           
        for i in data:
        	if i[0]=now and visited[i[1]-1]==False:
            	queue.append(i[1])
                visited[i[1]-1]=True
            elif i[1]==now and visited[i[0]-1]==False:
            	queue.append(i[0])
                visited[i[0]-1]=True
     answer+=1
  return answer

 

 

 

DFS(Depth First Search) 깊이 우선 탐색

• 하나의 경우에 대해 모든 경우의 수를 조사하고, 다음 경우의 수를 조사하는 방법
• 모든 노드를 방문하고자 할 때 사용하는 방법
• 스택 자료구조 방식을 사용한다

while len(stack)>0:
	now = stack.pop()	# 스택의 가장 마지막 데이터 추출
    if now == dest:
    	return True
    x = now[1]
    y = now[0]
    # 정답 여부 검사
    
    if x - 1 > -1:		# 왼쪽으로 이동할 수 있다면
    	if maps[y][x-1]==0:
        	stack.append([y,x-1])
            maps[y][x-1]=2
        if maps[y][x+1]==0:
        	stack.append([y,x+1])
            maps[y][x+1]=2
        if maps[y-1][x]==0:
        	stack.append([y-1,x])
            maps[y-1][x]=2
        if maps[y+1][x]==0:
        	stack.append([y+1,x])
            maps[y+1][x]=2
    return False