Alogorithm _ 3. DFS, BFS

1) 깊이우선탐색 (DFS)

Depth First Search의 약자로 깊이 우선 탐색을 의미하며, 하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정

 

※ 깊이우선탐색과 스택

위 예시에서 DCBA 의 Stack로 구현했을때 AB를 확인하고 C를 확인하는 것이 아닌 EJ를 다시 스택하여 경우의수를 찾는 구조로 해결한다.

 

깊이우선탐색의 가장 대표적인 예시는 미로찾기이다.

while len(stack)>0: # 스택에 데이터가 있따면
    now = stack.pop() #stack의 가장 마지막 데이터 추출

    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 # 갈 수 있는 길이라면 스택에 추가하고 방문여부 2를 표시
    if x+1 < hori: # 오른쪽으로 이동할 수 있다면
        if maps[y][x+1]==1:
            stack.append(y,x+1])
    if y-1 > -1:
        if maps[y-1][x]==1:
            stack.append([y-1,x])
            maps[y-1][x]
    if y+1 < verti:
        if maps[y+1][x]==1:
            stack.append([y+1,x])
            maps[y+1][x]=2

    return False

 

2) 너비우선탐색 (BFS)

Breadth First Search의 약자로 넓이 우선 탐색을 의미.

하나의 경우의 수 에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정

※ 너비우선탐색과 큐

A가 담긴 큐에서 A를 검사하고 BCD를 큐에 담는다. 선입선출로 이를 모두 검사한 뒤 EFGHI를 검사하고 G가 정답이므로 G를 검사할떄 검사를 종료한다.

 

너비우선 탐색의 대표적인 알고리즘 문제는 최단경로 찾기이다.

while len(queue)>0: # 큐에 데이터가 있다면
	count = len(queue) # 같은 거리에 있는 큐 데이터 갯수
    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 # 거리를 1 더 벌린다
return anwer