*이 포스팅은 백준 알고리즘 1260을 기준으로 코드를 설명하므로 입력/출력값에 대한건 백준으로 ㄱㄱ
DFS
-깊이 우선 탐색
루트노드(혹은 임의의 노드)에서 시작해 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법
=>넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
=>사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
->깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
->단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
방문한 다음 다시 backtracking해서 들리지 않은 노드가 있는지를 확인한다.
BFS
-너비우선 탐색
차이
DFS는 스택을 사용하고, BFS는 큐를 사용한다.
구현에 있어서, 인접행렬 또는 인접리스트를 통해 구현할 수 있다.
인접리스트/인접행렬
구현 //java 기반
int[][] a = new int[n + 1][n + 1];
for (int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
a[v1][v2] = 1;
a[v2][v1] = 1;
}
구현
ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
a[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
a[v1].add(v2);
a[v2].add(v1);
}
->이건 자바기반이니까 arraylist가 가능하지만 (아니 아직까지 c++라이브러리를 별로 크게 사용한게 없어서 그런지 내눈에는 아직까지도 자바가 좋아보인다..) 무튼 c++로 하려면 벡터 사용하면됨
벡터도 자바에서 사용하는게 더 편하지만..뭐 해보지뭐
//그래서 벡터 타임!!
C++에서 사용하는 방법은 또 다르니까 또 공부해야지뭐
- #include <vector>해줘야함
- using namespace std;해주면 편함
- vector 선언방법
vector<data type>변수 이름
Ex)vector<int> v;
//
다시 DFS로
구현하는 방법은 두가지
1.스택으로 구현-방문한 노드들을 스택에 넣었다가 다시 꺼내서 작업
2.순환 호출 이용
먼저 재귀함수 이용해서 해보자
충격적이다 티스토리에서는 코드 블럭이라는걸 사용할 수 있었다..
public static void dfs(int[][] a, boolean[] c, int v) {
int n = a.length - 1;
c[v] = true;
System.out.print(v + " ");
for (int i = 1; i <= n; i++) {
if (a[v][i] == 1 && !c[i]) { //인접행렬이 있는데 DFS니까 i로 또 Dfs탐색 해야함
dfs(a, c, i);
}
}
}
=>스택으로 바꾸기 //C++에서도 stack헤더파일 선언해주면 사용가능 초기화는 벡터랑 같은 방법임
push pop사용하면 됨
a는 인접행렬이고, c는 방문여부, v는 정점이 된다.
public static void dfs(int[][] a, boolean[] c, int v, boolean flag) {
Stack<Integer> stack = new Stack<>();
int n = a.length - 1;
stack.push(v);
c[v] = true;
System.out.print(v + " ");
while (!stack.isEmpty()) {
int vv = stack.peek();
flag = false;
for (int i = 1; i <= n; i++) {
if (a[vv][i] == 1 && !c[i]) {
stack.push(i); //인접행렬에 있으니까 이제 방문할것이므로 스택에 푸쉬를 한다.
System.out.print(i + " ");
c[i] = true;
flag = true;
break;
}
}
if (!flag) {
stack.pop(); //연결된 간선이 없고, 방문하지 않은 정점을 찾지 못한다면 pop
}
}
}
pop부분은 backtracking과정인것 같음
방문하지 않은 노드가 없으면 backtracking으로 다시 올라가서 확인하고 pop하고 그러다 스택이 비워지면 While문 나오면 끝임
//BFS
BFS는 큐를 사용한다.
FIFO 이용
c++ 에서 큐사용 가능
스택이랑 사용하는거 비슷
*큐에서 Pop은 큐에 있는 원소를 삭제하는 역할인듯
- front() : 큐 제일 앞에 있는 원소를 반환
- back() : 큐 제일 뒤에 있는 원소를 반환
public static void bfs(int[][] a, boolean[] c, int v) {
Queue<Integer> q = new LinkedList<>();
int n = a.length - 1;
q.add(v);
c[v] = true;
while (!q.isEmpty()) {
v = q.poll(); //c++에서는 Front..?제일 먼저 들어간거 나오는 역할인듯
System.out.print(v + " ");
for (int i = 1; i <= n; i++) {
if (a[v][i] == 1 && !c[i]) {
q.add(i); //c++에서는 push
c[i] = true;
}
}
}
}
//여기서는 break걸 필요가 없다.
->그냥 인접한게 있으면 그것부터 탐색하면 되는거니까
-bfs가 dfs보다 시간복잡도가 효율적
인접 행렬의 경우 정점을 탐색하는 과정에서 무조건 1에서 n까지 루프를 돌았다.
인접 리스트의 경우에는 리스트 특성상 각 리스트마다 존재하는 정점만큼 존재한다.
그렇기에 i에서 n까지 돌지 않아도 되고, 위와 같이 존재하는 만큼만 탐색하면 된다.
이제 내일은 문제를 풀어봐야겠다.
출처: https://mygumi.tistory.com/102 [마이구미의 HelloWorld]
내용출처
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
'알고리즘' 카테고리의 다른 글
| c++ 최대공약수, 최소공약수 구하기 (0) | 2020.05.08 |
|---|---|
| sw expert 1245번 문제 (0) | 2019.05.17 |
| 완전 탐색(brute-forse)과 Greedy algorithm (0) | 2019.05.17 |
| dynamic progoramming 알고리즘 (0) | 2019.05.10 |