[Python/알고리즘] DFS와 BFS 완전정복(프로그래머스 - 타겟넘버)

코테에 항상 묻지도 따지지도 않고 나오는 DFS/BFS 알고리즘을 탐색해볼 시간이다.

 

코테 맞춤형 개념 설명

두 알고리즘은 그래프 탐색 알고리즘이다.

중요하진 않지만, 무슨 뜻이냐면

그래프: 여러 개체들이 연결되어 있는 자료 구조

탐색: 특정 개체를 찾기 위한 알고리즘

즉, 여러 개체들이 연결된 그래프에서 특정 개체를 찾는 알고리즘이올시다.

 

그럼 어떤 문제를 DFS/BFS 알고리즘으로 풀어야하나? 

대표적 문제유형은 아래와 같다.

1. 경로탐색 유형(최단거리, 시간)

2. 네트워크 유형 (연결)

3. 조합 유형(모든 조합 만들기)

 

그럼 이제 여기서 의문, 어떤 걸 DFS로, 어떤걸 BFS로 풀어야하나?

사실, 웬만한 난이도의 문제는 두 알고리즘으로 풀 수 있다고 한다.

(이것 마저 까먹고 뭐드라미 하고 있던 나자신,, 반성하자)

 

하지만 그래도 차이점이 당연히 존재한다! 

뻔한 개념 설명은 패스하고, 코테를 풀기위한 방식으로만 접근하겠다.

1. DFS(깊이 우선 탐색)

DFS: 드라마 전편 하나만 몰아본다. -> 깊이 우선 탐색

DFS는 한놈만 패기 때문에 재귀함수가 일반적이다.

DFS 알고리즘

 

2. BFS(깊이 우선 탐색)

BFS: 여러 드라마 한개씩 다 챙겨봄 -> 너비 우선 탐석

BFS는 여러놈을 한 대씩 패는 것이라 Queue/Linked List가 일반적.(순서가 보장되어야하기 때문에)

 1.가장 먼저 넣었던 걸 꺼내서

 2. 연결된 점을 Queue에 넣기

 3. Queue가 빌 때까지 반복

 

BFS 알고리즘

 

 

 

 

-> 본인이 더 자신있고 손에 익고 편한 알고리즘 쓰면 됨.

DFS는 수행 시간 관점에서 복불복, 운이 좋으면 첫번째 경우고 안좋으면 마지막 경우임. -> 시간초과로 실패할 가능성있음.

BFS는 초반에는 느려보이지만 시간복잡도가 낮음. -> 코테 중 뒤쪽의 난이도 있는 문제라면 BFS 사용 권장

 

 

예제로 알아보기

자 그럼 예제로 탐색해보자.

풀어볼 문제는 프로그래머스 - 타겟 넘버이다.

문제 자세히 보기

 

문제설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

 

풀이

얼핏 보면 이게 왜 DFS/BFS 인가 싶지만, 각 숫자의 +/- 하여를 노드로서 취급하면 DFS/BFS문제로 쉽게 풀 수 있다!

즉, 엣지 형태가 아니더라도 이진트리로 구성 가능하면 DFS/BFS 알고리즘으로 풀 수 있는 것이다.

 

먼저, DFS로 접근해보겠다!!!!(전 이게 더 쉬운 거 같아요.. 단순해서)

간단한 문제이니, DFS로 풀어도 시간초과따윈 뜨지않았다! ㄱㅇㄷ

 

DFS는 재귀함수로 푼다! 라는 공식으로 내머릿속을 지배하고 있기 때문에

(아닐수도 있어요 다만 코테 한정 그렇게 생각하기로 했습니다)

 

재귀함수에서 가장 중요한 건 탈출 조건이다.

때문에, 탈출 조건을 먼저 세웠다.

가장 끝 노드(숫자)까지 탐색하면 탈출 하는 것이다! (참 쉽죠잉?)

이때, 모든 노드를 합했을 때 target과 동일하면 +1 해주면 끝이다.

 

탈출 조건을 세웠으니, 재귀함수 넣어주면 끝!

다만, 중요한 건 아래 나의 코드와 같이, 따로 함수를 두어 구현했기 때문에, 정답이 되는 cnt 변수를 global로 선언해주어야하는 것이다. 그리고 0 으로 초기화는 solution에서 해줘야한다.

(바보같이, dfs함수 내에서 초기화한 사람,, 그게 나에요)

 

이렇게 접근하고 나면, 되게 쉬운데 처음에 이걸 떠올리는 과정이 왜 아직도 어려운지 모르것다..

def solution(numbers, target):
    global cnt 
    cnt = 0
    dfs(numbers, target, 0, 0)
    return cnt

def dfs(numbers, target, depth, value):
    global cnt
    
    # 탈출 조건 #
    ## depth 끝까지 탐색했는데 target과 동일한 경우: cnt + 1
    if depth == len(numbers) and value == target:
        cnt += 1
        return
    
    elif depth == len(numbers):
        return
    
    # 재귀 함수 #
    dfs(numbers, target, depth+1, value+numbers[depth])
    dfs(numbers, target, depth+1, value-numbers[depth])

 

 

자 그럼, BFS 로 접근해보겠다.

왜인지모르게, 난 BFS가 무섭지만, 쫄지 않고 해보겠다.

DFS는 한 경우에만 집중해서 그게 target과 동일한지 확인하고, 그다음 경우로 넘어갔다면

BFS는 모든 경우의 수를 계산해두고, 그 중 target 과 같은 경우가 몇개인지 세어보면 된다.

def solution(numbers, target):

    ## 모든 계산 결과를 담을 리스트
    leaves = [0]
    cnt = 0
    
    ## 모든 경우의 수 계산
    for num in numbers:
        temp = []
        
        # 자식 노드 계산
        for leaf in leaves:
            temp.append(leaf + num)
            temp.append(leaf - num)
        
        # 다음 레벨로 이동
        leaves = temp
    
    for leaf in leaves:
        if leaf == target:
            cnt += 1
    return cnt

 

 

 

 

내 자신도, 이 긁을 읽으시는 모든 분들도

DFS/BFS 를 이해했길 바라며 그럼 이만 ...