[TIL]21.07.30

👨‍💻 오늘 공부한 것

BFS(Breadth First Search) 너비 우선 검색

BFS을 구현해보았다. (넘나 어려운 것..)

1.

const result = getDirections(
	[
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 0, 0, 1],
		[0, 1, 0, 0],
	],
	0,
	2
);
console.log(result); // true

다음과 같이 출력값이 나오기위해 구성한 주석코드들이다. 자신만의 언어로 얘기할 수 있어야한다고 생각해서
여러차례에 거쳐 코드를 작성하기 전에 주석으로 정리해 보았다.

// 첫번째
// bfs(breath first search)
// queue
// queue에 첫번째 vertex를 푸쉬함
// 방문을 했는지에 대한 boolean타입 요소로 가진 배열 isVisited를 선언
// 첫번째 vertex는 방문이 되었으니, isVisited[vertex] = true; 를 할당
// 큐의 길이가 0이면 while문 멈춘다. 큐의 길이가 0일때는 더이상 간선이 연결이 안되있어서 갈데가 없는 것이다.
// adjacency matrix[index]에서 adjacency matrix[index]를 다 돌면서
// if(adjacency matrix[index][i] === 1 && isVisited[i] === false);
// 즉 index 는 현재 vertex from를 의미하고, i 는 to를 의미한다.
// 그래서 from에서 to를 갈 수 있고, 아직 방문을 안했다면 queue에 push를 하고 방문을 했다는 의미로 isVisited[i]에 true를
// 할당한다.
// 그리고

// 두번째
// adjacency matrix를 input으로 받아서 from vertex에서 to vertex까지 갈 수 있는 지 불린타입을 리턴하라.

// 큐를 선언하고 from을 푸쉬한다.
// from vertex를 방문했으니 vertex를 마크처리해준다.
// 이제 시작
// 큐에 들어간 노드를 꺼내고 그 노드의 자식 노드들이 아직 방문되지않았다면, 마크처리가 되지않았다면 큐에 푸쉬해준다.
// 그리고 큐에 푸쉬된 노드들을 방문이 되었다고 마크처리해준다.
// 큐에서 노드를 꺼낸다. 꺼낸 노드는 출력하고 꺼낸 노드의 자식노드들이 마크처리, 방문이, 순회가 되지 않았다면 큐에 푸쉬해주고
// 방문, 순회가 되었다고 마크처리해준다. 그래서 모든 노드가 방문이 되어 더이상 큐에 들어갈 vertex가 없을경우 순회, 프로그램
// 을 종료해준다.

// 세번째
// 큐를 생성하고 생성한 큐에 from을 배열의 요소로 할당한다.
// from vertex가 조회되었다고 따로 배열을 만들어 true로 기록해놓는다.
// queue의 길이가 0이면 종료하는 while문을 사용한다. queue의 길이가 0이라는 것은 vertex가 edges가 없어서 다른 vertex
// 를 push받지 못했다는 뜻이므로 순회를 종료한다.
// queue에서 shift를 하여 노드를 꺼낸다.
// 꺼낸 노드가 to와 같다면 true를 리턴한다. 목적지는 to인데, from에서 to에 도착했다는 것은 어떻게든 간선이 연결되어있다는 것
// 을 의미하기 때문이다.
// 꺼낸 노드에서 순회되지않고 간선이 있는 노드들을 queue에 푸쉬하는 if문을 작성한다.
// 이때에 함수에서 받은 input은 adjacency matrix이므로 인접행렬의 특성을 고려하여 for문을 사용해 어디에 간선이 연결되어
// 있는지 고려한다.

2.

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

// 첫번째
// edges안에 있는 최대 버텍스를 구한다.
// 최대 버텍스 수만큼 순회했다고 마킹할 수 있는 배열을 만든다.
// 간선이랑 연결된 그래프의 수를 세기위해 카운트 변수를 선언한다.
// Adjacency List를 만든다.
// 0vertex부터 최대 vertex만큼 순환하기 위하여 for문을 선언한다.
// for문에서 만약 순회되지 않은 버텍스라면 bfs를 호출해서 count를 증감시킨다.
// 모든 버텍스가 순환되면 count를 리턴한다
// bfs는 Breath First Search의 약자로 구현은 큐로하면 된다.
/*
큐를 생성

현재 해당노드를 큐에 넣고 그 해당노드를 큐에 들어갔다고 마크를 한다

밑에서 하나 꺼내고 꺼낸 노드의 자식 노드들을 큐에 넣고 깨낸 노드는 출력해준다. 이때 큐에 들어간
노드는 마크처리를 한다.

다시 큐에 들어간 노드를 꺼내고 꺼낸 노드의 자식 노드들을 큐에 집어 넣는다. 그리고 꺼낸 노드는 출력해주고, 이때 큐에들어간 노드는 마크처리해준다.

그리고 다시 큐에 들어간 노드를 꺼낸다. 꺼낸 노드의 자식노드를 큐에 넣어주고 마크처리해준다. 이때 꺼낸 노드는 출력해준다.

*/

/*

두번째
1. edges안에 있는 최대 vertex를 구한다.
2. adjacency list 를 만들어서 vertex 수 만큼 key, property를 만든다.
2-1. 만든 adjacency list에 edges는 무향그래프를 담아둔 것이므로 그에 따라 adjacency list를 만든다.
3. 조회된 vertex를 확인할 수 있는 배열과 연결된 정점의 컴포넌트 수를 카운트할 수 있는 카운터 변수를 선언한다.
4. 0부터 최대 버텍스 수만큼 순환하여 간선에 따라 정점을 순회할 수 있도록 for문을 만든다.
5. for문안에서 만약 순회되지 않은 vertex가 있다면 bfs함수를 호출하고, 카운터변수를 1씩 더한다.
6. 이때 bfs함수는 순환된, 조회된 버텍스를 확인하기위한 배열을 인자로 받아서, 조회되었다면 해당 인덱스를 true로 할당하여
7. 중복되어 조회되지 않도록한다.
8. 마지막으로 연결된 정점의 컴포넌트의 수를 숫자로 반환하여 리턴한다.
*/