깊이 우선 탐색 DFS , 너비 우선 탐색 BFS

DFS(Depth - First Search)와 BFS(Breadth - First Search)

 

그래프 탐색

 

 

깊이 우선 탐색 // 너비 우선 탐색

 

ex)

가다가 갈림길을 만났을 때

dfs -> 갈 때까지 다 가보고 다시 돌아오거나 하는 것

bfs -> 양쪽을 다 보고 가다가 또 갈리면 그 경우까지 다  

 

문제로 나올 때는 미로 찾기 / 출구 찾기 / 어디 있는 물건 찾기 등

 

방문되는 순서가 다를 것이다.

 

 

---

그래프를 matrix로 표현하기

 

1. 기본 상태 - 완벽 대칭 시멘틱 하다.

• 0과 1은 서로 연결되어있다. 양쪽 다 연결되어있다. 대칭

---

2. 방향성이 있는 경우 -  대칭 x 시멘틱 하지 않다.

• 방향성이 있다. - 한쪽으로만 이동할 수 있다. 0에서 2는 가능하지만, 2에서 0은 불가능 - 비대칭

---

3. 웨이트가 있는 경우 - 가중치가 있을 경우도 비대칭

•  ex) 편도인 도로에서 a->b 갈 때 3분 걸리고 b->a 갈 때는 5분 걸리고 하는.

 

 

---

 

그래프를 링크드 리스트로 표현하기

 

1. 기본

 

2. 웨이트 있는 경우 - 클래스에 노드 번호 + 가중치 정보 같이 넣을 수 있다.

 

 

 

---

 

탐색 시작 - 

 

깊이 우선 탐색(DFS)

• 인접한 노드를 우선 탐색하는 방식
• 스택을 활용하여 구현할 수 있음
• traverse - 방문했다고 표시해줌 - visited 
• DFS 탐색 순서 : 0 - 1 - 3 - 7 - 4 - 5 - 2 - 6 or 0 - 2 - 6 - 5 - 4 - 1 - 3 - 7

 

• 탐색방법
• 방문한 것들은 visited 표시해주기 
•  0137 끝까지(7까지) 가보고 빽 -> 3 방문 -> 방문 표시 있는 애(visited)는 넘어가고 1로 이동 -> 1도 표시 있으니까 4로 넘어간다. -> 그다음에 끝까지 526 

 

 

 

---

 

 

 

너비 우선 탐색(BFS)

• 한 노들에 모든 인접한 노드를 탐색하는 방식
• 큐를 활용하여 구현할 수 있음
• BFS 탐색 순서 : 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7
• 0의 입장에서 인접 1과 2 탐색 // 1의 입장에서 3과 4 탐색 // 2의 입장에서 5와 6 탐색~~ 

 

• 탐색방법
• 시작하고 인접한 애들 다 본다. 0 시작하면 1과 2 다 본다 ( 012 ) -> 찾았던 것 중에 1의 입장에서 본다 34 / 2의 입장에서 본다 56 ( 3456 ) -> 3의 입장에서 본다 (7) / 4-5-6의 입장에서 본다 끝 

 

 

 

 

---

 

 

구현 시작

 

깊이 우선 탐색(DFS) 구현원리

스택을 사용 

스택 메모리에 넣을 애가 없으면 기존에 들어가 있던 애를 메모리에서 꺼낸다. 

 

 

 

 

---

 

( 공통 ) 무엇이 될지 모르는 클래스 그래프 하나 만들어주고.

 

---

(Dfs 1번 ) =  변수와 생성자 선언  

---

(Dfs 2번) = 서치 하는 함수 생성 = dfsTraversal( )

---

(Dfs 3번) = main 넣고 테스트 출력

 

 

 

 

---

 

 

너비 우선 탐색(BFS) 구현원리

 

 

 

④ 2를 꺼내면서 5와 6을 입력해주는 부분을 추가하자 ㅎㅎ

 

+@ 0 을꺼내면서 0과 인접한 노드가 추가될 때 2가 먼저 들어가면 0 - 2 - 1 - 5- 6 이런 식으로 순서가 달라질 수 있음

 

 

( 공통 ) 무엇이 될지 모르는 클래스 그래프 하나 만들어주고.

 

---

(Bfs 1번 ) = 변수와 생성자 선언  

 

 

---

 

(Bfs 2번 ) =서치 하는 함수 생성 = bfsTraversal( )  

 

---

(Dfs 3번) = main 넣고 테스트 출력

 

 

 

---

총 정리 및 체크 포인트


Dfs - 깊이 우선 탐색 

stack 메모리를 이용하여 넣어주고 꺼내 주는 것이 핵심
①메모리에 있는 애를 꺼내면서, ②꺼낸 거에 인접한 애들을 넣어주고
③마지막에 넣은 거를 또 꺼내면서, ④그거에 인접한 애들을 넣어주고 반복
⑤넣어주는 애가 없으면 스택 메모리에 있던 애를 꺼내고,
⑥꺼낸애에 인접한 애를 넣어주고 빼고 넣고를 반복
LIFO의 특징을 활용! 


Dfs - 코드 부분 체크 포인트!

①stack.push(0); -> 맨 마지막에 추가된 애가 제일 먼저 꺼내진다.
②matrix [ node ][ j ] != 0 -> node와 인접한 애인지 아닌지 체크
③stack.push( j ) -> 스택 메모리에 j 넣어준다.
④visited[ j ] = true; -> 메모리에 추가한 j는 visited 표시해 준다.

for문 다 돌고 추가된 push( j )와 pop( 0 ) 이 동일!
2개가 push 됐어도 2번째 들어간 애가 먼저 pop으로~! 

---

Bfs - 너비 우선 탐색

ArrayList를 이용하여 구현한 것이 핵심
①배열 맨 앞에 있는 애를 꺼내면서, ②꺼낸 거에 인접한 애들을 맨 뒤에 넣어준다.
③다시 배열 맨 앞에 있는 애를 꺼내 주고, 꺼낸 거에 인접한 애들을 맨 뒤에 넣어준다.
④배열 queue의 size 가 0이 될 때까지 반복
FIFO의 특징을 활용!


Bfs - 코드 부분 체크 포인트!

①queue.remove( 0 ) -> 배열 맨 앞에 애를 꺼낸다.
②matrix [ node ][ j ]!= 0 -> 인접한 애들을 + queue.add( j ) -> 배열 맨 뒤에 넣어준다.
③queue.remove( 0 ), queue.add( j )
④while( queue.size() != 0 ) 

for문 다 돌고 추가된 add( j ) 와 remove( 0 ) 은 다르다.
2개가 add 됐어도 그건 배열 뒤에 추가된 거고, remove( 0 )은 배열 맨 앞에 애 꺼내온다.

 

---

 

review


이번 강의를 통해 그래프에 대해 한 층 더 다가갔다.
2가지 탐색법에 대해 이해한 내용을 정리하려고 하니
글의 길이가 2배가 되었다.ㅎㅎ

dfs와 bfs를 매트릭스와 링크드 리스트로 표현하는 법
탐색이 이루어지는 각각의 방식과 순서에 대한 이해
그것을 이루어지게 구현하는 - 코드에 대한 이해

역시 구현하는 부분이 가장 이해하기 힘들었다 ;(

FIFO 선입선출/ LIFO 후입 선출
글로만 보고 이해했던 내용을 스택과 arrayList(queue)를 이용해서 실제로 구현해보았다.
글과 그림으로 볼 때는 원리도 작동 방식도 이해하기 쉬웠지만...
구현 코드에서 만난 그래프란 녀석 처음엔 쉽지 않았다.

이제 이 방법들을 이용한 문제들을 풀어보면서 한층 더 다가가 보도록 하자!