[DFS/BFS] 타겟 넘버

 

 

  DFS/BFS 두 가지 방식 모두 그래프를 탐색하는 방법이다.

그저 그래프를 탐색하는 것 만으로도 해결될 수 있는 문제가 많기 때문에 그래프 탐색은 중요하다.

---

그래프

그래프는 정점과 간선들 사이의 유한 집합으로 이루어진 자료구조의 일종.

정점은 노드라고도 불리며, 간선은 링크라고도 불린다.

(정점:vertex, 노드:node, 간선:edge, 링크:link)

 

그래프의 표현방식

• 인접 행렬: 2차원 배열

그래프의 정점 수: n

n*n의 2차원 배열인 인접행렬로 표현할 수 있다.

 

ex) M[i][l] = 1 (i과 l이 연결되어 있을 때)

     M[i][l] = 0 (연결되지 않을 때)

 

정점이 3개라면 다음처럼 표현될 수 있다.

[[1, 1, 0], [1, 1, 0], [0, 0, 1]]

 

1 1 0

1 1 0

0 0 1

 

n번째 배열의 n번째 요소는 자기자신이기 때문에 항상 1

참고: https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

여기서 주어지는 형태가 인접행렬

 

• 인접 리스트: 연결 리스트

각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것.

각 노드들은 인접 정점을 저장하게 된다.

 

ex)

https://kingpodo.tistory.com/46

6-2. 그래프의 표현(인접 행렬, 인접 리스트, 인접 다중 리스트)

 

인접 행렬이 항상 n^2개의 저장공간을 요구하는 것과는 다르게 인접 리스트는

(정점: n 간선:e일때) n개의 헤더 노드와 2e개의 노드만 필요하기 때문에

간선의 개수가 적은 희소 그래프에 적합하다.

*무방향이기 때문에 2e개, 단방향이면 e개

 

 

 

 

 

 

 

 

---

1. DFS - 깊이 우선 탐색

DFS[Depth First Search] - 깊이 우선 탐색

 

  트리 탐색과 비슷하다.

  시작 정점에서 한 방향으로 계속 가다 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 가른 방향으로 다시 탐색을 진행하는 방법. (사진자료: https://devuna.tistory.com/32)

미로찾기 등

 

 시작 정점에서 시작해서 한 깊이를 완벽하게 탐색하는 방식.

 

 

특징

• BFS보다 간단하게*재귀 구현이 가능하다.
• 검색 속도는 BFS보다 느리다. (한 깊이-경로-로 깊게 파고 들어갈 수 있기 때문에)
• 현 경로상의 노드만을 기억하기 때문에 저장공간의 수요가 비교적 적음.
• 얻어진 답으로 가는 경로가 최단 경로가 아닐 가능성이 있다. (적은 수부터 깊이 탐색을 한다면)

 

구현

스택 또는 재귀함수

 

(자료 : https://choiiis.github.io/algorithm/practice-dfs/)

스택 > 깊이 순으로 집어넣다가 인접 노드가 없으면 인접 노드가 있는 곳까지 스택에서 제거

방문한 노드는 꼭 방문처리 해주어야 무한 루프에 빠지지 않는다.

 

재귀> 더 이상 방문할 노드가 없으면 함수를 종료한다. (값을 return받아 경로의 정보나 특성을 얻기에 유용)

 

 

시간 복잡도

인접 리스트: O(n+e)

인접 행렬: O(n^2)

*희소 그래프인 경우 우선 탐색은 인접 리스트의 사용이 인접 행렬보다 빠르다.

 

 

 

 

 

---

2. BFS - 너비 우선 탐색

BFS[Breath First Search] - 너비 우선 탐색

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

시작으로부터 인접한 정점를 먼저 탐색하고 멀리 떨어져 있는 곳을 나중에 탐색.

최단 경로를 찾을 때 이 방법을 주로 사용한다.

 

 

구현

큐

 

깊이 별로 큐에 집어넣은 후, 인접 노드를 집어넣고, 그 이전 깊이에 있었던 노드는

제거하는 식으로 탐색을 진행한다.

 

 

 

시간 복잡도

인접 리스트: O(n+e)

인접행렬: O(n^2)

모든 노드를 탐색하는 과정이기 때문에

표현하는 방식에 영향을 받을 수 밖에 없다.

같은 이유로 두 방식에서의 시간 복잡도는 차이가 없다.

 

 

특징

• 직관적이지 않은 면이 있다
• 지나온 경로를 체크하여 무한 루프에 빠지지 않게 하는게 중요하다.
• 큐를 사용한다.(선입선출 원칙)

 

 

 

둘을 사용하기 좋은 문제

1) 그래프의 모든 정점 방문 (DFS, BFS)

2) 경로의 특징 저장 (DFS), BFS는 경로의 특징을 가지지 못함

3) 최단거리 구하기 (BFS)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

DFS방식

def solution(numbers, target):
    def DFS(total, depth):
        if (depth == len(numbers)): #만약 끝에 다다르고
            if (total == target): #합이 target과 같다면
                return 1
            else: return 0;
        else:
            return (DFS(total+numbers[depth], depth+1) + 
                    DFS(total-numbers[depth], depth+1))
    
    answer = DFS(0,0)
    return answer

 

 

BFS방식

 

 

 

 

-

참고자료

https://devuna.tistory.com/32

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

https://yunyoung1819.tistory.com/86

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0​

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html