< DFS(깊이 우선 탐색) BFS(넓이 우선 탐색) >

< 개념 >

*정석 이론

dfs는 stack을 사용한다. 재귀적 방법이다..

- 방문한 노드의인접 노드 중 가장 가까운 노드(보통 숫자가 작은 노드)를 stack에 넣고 방문한다.

- 그 방문 노드의 인접 노드 중 가장 가까운 노드(보통 숫자가 작은 노드)를 stack에 넣고 또 방문한다.

- 방문할 인접 노드가 없다면 (=leaf에 다다른 것이다) stack에 넣어놨던 노드를 꺼내어 반복한다. (가장 최근에 들어간 노드가 나오므로, 그 부모 노드가 나와서 거꾸로 거슬러 올라갈 수 있다.)

 

bfs는 queue를 사용한다.

- 방문한 노드의 모든 인접 노드를 queue에 삽입한다.

- queue에서 다음노드를 꺼내어 다시 모든 인접 노드를 탐색한다.

- 방문할 노드가 없을 때까지 반복한다.

 

*

그래프-노드 표현은 인접그래프, 인접행렬로 가능하다.

visit표시를 해줘서 이전에 방문한 곳인지 아닌지 검사한다.

 

< 실전문제 > 

*프로그래머스 dfs/bfs - 타겟넘버

- 사고 과정

일단 왜 dfs, bfs인지 모르겠음...

순차적으로 타겟보다 합 값이 작은 지 큰지 검사.. 는 처음부터 - 붙는 경우를 볼 수 없는데 ..

- 해답 본 후

1. dfs,bfs인 이유

해당 숫자가 +,-되는 모든 경우를 그래프로 표현한다. 이 경우에 대한 이후 숫자의 +,- 경우도 각각 따라붙는다.

그 그래프를 전부 탐색했을 때의 결과와 타겟넘버가 같다면 올바른 경우이다. 아니라면 올바르지 못한 경우. 

2. 그래프 표현하기

이것도 헤맸다 .. 어떻게 그래프로 표현되는 지 생각을 못 했는데, 순차적으로 계산되므로 현재 값에 +,- 경우를 각각 따로 구해서 더한 값을 넣어주면 된다 ..

 

def solution(numbers, target):
    result = [0]
    total = 0
    carculate = []
    for i in range(len(numbers)):
        get = numbers[i] #모든 numbers를 

        for j in range(len(result)): #현재 저장된 모든 계산 결과값에
            if i == len(numbers)-1: #마지막 리프는 다 저장하지 않고 계산해서 값이 타겟과 동일하면 total 카운트만 업해줬다.
                if result[j] + get == target:
                    total += 1
                if result[j] - get == target:
                    total += 1
            else: 
                carculate.append(result[j] + get) # + 하는 경우
                carculate.append(result[j] - get) # - 하는 경우
                if j == len(result)-1: #이전 단계에서의 결과값 저장된 것을 지워주기 위해서
                    result = carculate
                    carculate = []

    return total

 

#엄청난 풀이 ... 재귀(DFS)를 활용

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])
		#numbers를 for문 돌리는 대신 1:로 계속 깎아준다 ..
        #경우의 수 개수를 어떻게 뽑아주는 거지?