[Graph] 인접 행렬 길찾기 : 너비 우선 탐색(BFS)

BFS/DFS 좀더 이해를 하기 위해서 주석을 하나하나 달면서 공부를 해봐야겠다.

 

QUE/ WHILE/isVisited 무조건 쓴다고 생각하면된다. (문법처럼 국룰로 그냥 잡고들어감 ㅠㅠ)

 

bfs를 구하는 공식.

특정한 수가 주어진다면?

예를들어 1정점에서 4정점으로 가는 길이 있는지 없는지 구해라?

1과 4라는 시작점과 도착점이있다.

 

from = 1

to = 4

 

라고 fix를 하고 시작하자. 

 

1. que만들기

 

// let que =[ ] <= 완성된게 아니다. 

 

2. que안에 시작점을 넣어서 만든다.

 

let que = [from] //완성됨.

 

3. isVisited 방문 체크리스트가 필요하다. (true?false?방문함?방문안함?)

 

let isVisited = new Array(matrix.length).fill(false) <= true/false 로 방문했나 안했나

 

4 시작점 = 방문함

 

만들어줬으니 방문한건 체크해줘야됨. 

isVisited[form] = true

 

5. while문 만들기 (que.length>0)까지

 

이제 탐색을 시작해야할 차례다. 

que.length가 0이되면? 작을수는 없고? 그러면 끝나야한다. 더이상 확인할만한것이 없다는 의미 = 확인이 끝났거나? 접점이없거나 

 

6. 현재값을 만들어준다.

 

지금 현재 확인할것. => 그것은 바로 시작점(왜냐면 나온숫자가 from to밖에 없어용..)

let now = que.shift()

 

7.  조건을 만들어준다. count라던가, 다른무언가. 

if(from === to) return true;

가다가다가다가 to에 다달았어? 그럼 true. 왜냐 que[from]이 들어가고 shift()를 한것으로보아서 from값은 계속해서 변할것이다.

form이 to를 향해 가는것이다. 그것이 다다르면? 조건이 만족해서 ture를 뱉어낸다.

 

8. 중요한 반복문 돌리기 

 

[
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 0, 0, 1],
		[0, 1, 0, 0],
	],
	0,
	2
);

 

for(let i=0; i<matrix[now].length i++)

 

사실상 행과 열인데. from이 어디로연결되어있는지 찾을것이다.  지금하고잇는것에 대해 잘살펴보면. 내가 머릿속에서 위에서 연결되있는지 확인할때 하고잇는 행위를 봐보자 0일때 0번째줄에서 1번째 열 2번째열 4번째열 4번째 열에 1이 있는지를 찾는중이다. 

matrix[now] 행부터 확인을 하고있으니! i<matrix[now].length가 된다. 

 

==> 이부분이 if(matrix[now][i] ===1 ) <===이코드.

 

그런데!!

 

isVIsited[i] === false 는 왜 필요할까?

 

방문하지 않았던 값을 que에 올려서 그부분을 다시 탐색해야한다. 확인하면서 to 가까이로...(가는길이없을진 모르겠지만 시도는해야지?) 

 

 

 

그리하여 참/거짓 

완성된 BFS코드. 

문제를 풀며 여기서 조금씩 응용하는법을 연습하면서 익혀보자

 

function getDirections(matrix, from, to) {
  // TODO: 여기에 코드를 작성합니다.
  //bfs만드는방법.
  //que를 생성하자.
  let que = [from];
  let isVisited = new Array(matrix.length).fill(false); //[false,false,false,false]
  isVisited[from] = true
  
  while(que.length>0){
    let now= que.shift(); //0
    if(now === to) return true;
    for(let i=0; i<matrix[now].length;i++){
      if(matrix[now][i] ===1 && isVisited[i]===false){
        que.push(i)
        isVisited[i] = true;
      }
    }
  }
  
  return false;
}

---

응용된것을 풀어보자.

 

천천히!! 할수있다!!

 

세로와 가로의 길이가 각각 M, N인 마을지도가 배열로 주어졌을 때, '1'은 주민이 있는 집을 의미하고 '0'은 주민이 없는 땅을 의미합니다. 이 마을은 소문이 시작되면 하루에 상하좌우 한 칸 바로 옆에 있는 집으로 퍼집니다. 특정 주민의 집 (R, C)으로부터 어떤 소문이 시작될 경우, 마을 전체로 소문이 퍼지는데 걸리는 시간(일)을 리턴해야 합니다.

입출력 예시

let village = [
  '0101', // 첫 번째 줄
  '0111',
  '0110',
  '0100',
];
let row = 1;
let col = 2;
let output = gossipProtocol(village, row, col);
console.log(output); // --> 3
/*
1. 시작: (1, 2)에서 시작, 소문이 퍼진 곳을 x로 표기
 [
  '0101',
  '01x1',
  '0110',
  '0100',
 ]

2. 1일 뒤
 [
  '0101',
  '0xxx',
  '01x0',
  '0100',
 ]

3. 2일 뒤
 [
  '0x0x',
  '0xxx',
  '0xx0',
  '0100',
 ]

4. 3일 뒤: 소문이 전부 퍼짐 (끝)
 [
  '0x0x',
  '0xxx',
  '0xx0',
  '0x00',
 ]
/*