DFS & BFS

이번 포스팅은 자료구조의 깊이우선탐색(DFS), 너비우선탐색(BFS)를 정리해보겠습니다.

1.깊이우선탐색(DFS)

깊이우선탐색(DFS)의 개념

깊이우선탐색(DFS)란? Depth First Search의 약자로 하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정 입니다.

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와 다른방향으로 다시 탐색을 진행하는 방법과 유사하다고 보면 됩니다. 모든 노드를 방문 하고자 할 경우 많이 사용합니다.

깊이우선탐색(DFS)과 스택

깊이우선탐색(DFS)을 스택을 활용하여 풀이가 가능 합니다.
스택을 활용하는 과정은 추후 포스팅 업데이트를 통해서 설명하겠습니다.

깊이우선탐색(DFS) 활용

깊이 우선 탐색을 활용하는 대표적인 예가 바로 미로찾기 입니다.

이때 미로를 찾기 위해서 스택을 활용하여 깊이우선탐색을 통해 길을 찾습니다. 코드로 구현하면 아래와 같습니다.

def mapSearch(stack):
    while len(stack)>0: # 스택에 데이터가 있다면
        now = stack.pop() # 스택의 가장 마지막 데이터 추출
        # 정답 여부 검사
        if now == dest: # now가 도착지점인지 검사
            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: # index가 맵에서 벗어나는 지 아닌지 확인
            if maps[y][x+1] == 1:
                stack.append([y,x+1])
                maps[y][x+1] = 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 # 스택에 데이터가 없다면 빠져나오기

2.너비우선탐색(BFS)

너비우선탐색(BFS)의 개념

너비우선탐색(BFS)란? Breadth First Search의 약자로 하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정 입니다.

시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법입니다.

너비우선탐색(BFS)과 큐

너비우선탐색(BFS)을 큐를 활용하여 풀이가 가능 합니다.
큐를 활용하는 과정은 추후 포스팅 업데이트를 통해서 설명하겠습니다.

너비우선탐색(BFS) 활용

너비 우선 탐색을 활용하는 대표적인 예가 바로 최단경로 찾기 입니다.

이때 경로를 찾기 위해서 큐을 활용하여 너비우선탐색을 통해 경로를 찾습니다. 코드로 구현하면 아래와 같습니다.

def routeSearch(queue):
    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[i] == now and visited[i[0]-1]==False:
                    queue.append(i[0])
                    visited[i[0]-1]=True
        answer += 1 # 거리를 1더 벌린다
    return answer