3주차 BFS (너비 우선 탐색) / DFS (깊이 우선 탐색)

BFS/DFS

 

 

BFS (Breadth First Search)

 

  : 너비 우선 탐색, (queue와 많이쓰임)

하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정
말 그대로 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 많이 사용

 

✔ 예제 : 최단 경로 찾기

1번 섬에서부터 12번 섬까지 가는 최단 경로는 얼마인가?
(단, 모든 경로의 거리는 1이다)

 

 

while len(queue) > 0: # queue에 데이터가 있다면 
    count = len(queue) # 같은 거리에 있는 큐 데이터 갯수
    for time in range(count):
        now = queue.pop(0) # 8-10 같은 거리에 있는 큐 갯수만큼 검사
        if now == dest:
            return answer # 11-12 정답이 존재하면 값 반환
        for i in data: # 연결된 포인트 완전 탐색 
            if i[0] == now and visited[i[1]-1] == False:
                queue.append(i[1])
                visited[i[1]-1]=True #14-16 방문하지 않은 연결된 길이라면 큐에 추가하고 방문표시
            elif i[1] == now and visited[i[0]-1] == False:
                queue.append(i[0])
                visited[i[0]-1] = True
    answer += 1 # 거리를 1 더 벌린다.
return answer

 

 

DFS (Depth First Search)

 

: 깊이 우선 탐색, (stack과 많이쓰임)

하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정
미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면
다시 가장 가까운 갈림길로 돌아와 다른방향으로 다시 탐색을 진행하는 방법과 유사
모든 노드를 방문 하고자 할 경우 많이 사용

 

✔ 예제 : 미로찾기

주어진 미로가 탈출가능한 미로라면 True
탈출 불가능한 미로라면 False를 반환

 

 

while len(stack)>0: # 스택에 데이터가 있다면
    now = stack.pop() # 스택의 가장 마지막 데이터 추출
    if now == dest:
        return True
    x = now[1]
y = now[0] #3~5 정답여부검사
    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])
            maps[y][x+1]=2 # 갈수있는 길이라면, 스택에 추가하고 방문여부를 2로 표시
    if y - 1 > -1: # 위로으로 이동할 수 있다면
        if maps[y-1][x]==1:
            stack.append(y-1,x)
            maps[y-1][x]=2
    if y + 1 < verti: # 아래로 이동할 수있다면
        if maps[y+1][x] == 1:
            stack.append([y+1, x])
            maps[y+1][x]=2
return False # 스택에 데이터가 없으면 false