[Graph] 너비 우선 탐색(BFS) /깊이우선탐색(DFS)

자료구조 파트는 사실 상, 알고리즘 문제 풀이와 직접적인 연관이있는 파트여서 개념이해 -> 문제풀이 위주로 공부해야겠다.

 

처음 알고리즘 문제를 접했을때 멘붕이왔지만, 레퍼런스 코드를 보며 계속해서 공부해보니 조금 친숙해져서 이제서야 정신차리고 포스팅을 시작.

어려운 개념이여서 천천히 원리를 이해하는게 우선이다 

 

어려워도 포기는 노노 !  시작해보자

 

그래프

정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종

출처 https://developer-mac.tistory.com/64

 

깊이우선탐색 DFS 

 

• 최대한 깊이 내려간 뒤 더이상 갈곳이 없을때는 옆으로 이동

가계도로 생각해보면 부모님 형제보다 나 먼저 탐색하는거 우리집안부터 정확하게 보는 구조

 

• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함

출처 https://developer-mac.tistory.com/64

너비우선탐색 BFS

• 최대한 넓게 이동한 뒤더이상 갈곳이 없을때는 아래로 이동

가계도로 생각해보면 아빠/엄마 형제관계부터 쭉 탐색하고 그 다음에 내차례

• 인접 노드 먼저 탐색 방법
• 최단경로 찾을 시 사용

 

두 방식의 차이점 (⭐⭐⭐)

출처 https://namu.wiki/w/BFS

DFS	BFS
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀로 구현	큐를 이용해 구현

 

알고리즘 유형

 

1. 그래프의 모든 정점 방문? => 둘중 하나 골라쓴다.
2. 최단거리 ? => BFS 큐를 이용하자
3. 경로특징? => DFS 재귀 사용하자

경로특징 : a-b로가는 경로, 중복되는게없어야한다 등의 이런 경로에 특징이 추가되면 DFS 

 

 

이제 아래 문제를 통해 공부해보자 

 

---

연결된 정점들

문제

방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.

입력

인자 1: edges

• 2차원 Array 타입을 요소로 갖는 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록 (2차원 배열, 정수 요소)
• ex) [[0, 1], [1, 2], [3, 4]]

출력

• Number 타입을 리턴해야 합니다.
• 연결된 정점의 컴포넌트의 수를 숫자로 반환합니다.

주의 사항

• 주어진 간선은 무향입니다.
  • [1, 2] 는 정점 1에서 정점 2로도 갈 수 있으며, 정점 2에서 정점 1로도 갈 수 있습니다.

입출력 예시

const result = connectedVertices([
	[0, 1],
	[2, 3],
	[4, 5],
]);
console.log(result); // 3

해당 정점들은 아래와 같은 모양을 하고 있습니다.

 

const result = connectedVertices([
	[0, 1],
	[2, 3],
	[3, 4],
	[3, 5],
]);
console.log(result); // 2

해당 정점들은 아래와 같은 모양을 하고 있습니다.

 

 

Step1. 매트릭스를 만들자.

 

탐색에서 가장중요한것 : 두번다시 방문하지않는다. isVisited라는 체크박스 만들어주기

//매트릭스 만들기!!!
function connectedVertices(edges) {
// TODO: 여기에 코드를 작성합니다.
let max= 0;
for(let i=0; i<edges.length; i++){
  let curMax = Math.max(...edges[i])
  curMax>max ? (max = curMax) : null;
}
  const matrix = new Array(max + 1).fill(0).map(e => new Array(max + 1).fill(0));
  let count =0;
  //엣지 넣기 ㅎㅎ
  edges.forEach(e => {
    matrix[e[0]][e[1]] = 1;
    matrix[e[1]][e[0]] = 1;
  })


 const isVisited = new Array(matrix.length).fill(false);

  for(let i=0; i<matrix.length;i++){
    if(isVisited[i] === false){
      dfs(matrix,i,isVisited) // bfs(matrix,i,isVisited) 둘중하나 고르면된다.
         count++;
      }
    }
  return count;
}

Step2

 

bfs 만들어보기 

 

bfs? <=  위에서 봤듯이 큐를 사용 하는것이 핵심 <= 큐? while과 짝궁<= 큐에서 썻던 now =que.shift, que.unshift 반드시 사용해줄것.

isVisited[v] 부분은 dfs랑 비슷한 원리다

 

 function bfs(matrix,v,isVisited){
   let que = [v] 
   isVisited[v] = true
   while(que.length>0){
    let now = que.shift()
   for(let i=0; i<matrix[now].length; i++){
     if(isVisited[i]=== false && matrix[now][i] === 1){
       que.unshift(i)
      isVisited[i] = true
        }
     }
   }
 }

 

Step3. 

 

dfs 만들어보기

 

dfs? <= 재귀사용

isVisited[v] 체크박스는 두개다 공통으로 사용해야한다.

 

 

function dfs(matrix, vertex, isVisited) {
	// 해당 버텍스에 방문 표시
	isVisited[vertex] = true;

	// 해당 버텍스의 모든 간선들을 전부 순회
	for (let i = 0; i < matrix[vertex].length; i++) {

		// 만약 i번째 간선과 이어진 버텍스를 방문하지 않았다면
		if(isVisited[i] !== true && matrix[vertex][i] === 1){
			// 재귀
			dfs(matrix, i, isVisited);
		}
		// 모든 방문이 종료되면 다음 버텍스를 확인한다.
		// 재귀가 종료되면(한 정점에서 이어진 모든 간선들을 확인했다면) dfs 함수를 종료하고 카운트를 센다. 
	}
}