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

이문제 또한 BFS/DFS 두가지 모두로 구현이 가능하다.

BFS/DFS 연습을 위해 두가지모두 분석해서 공부해보자

 

 

문제

세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미합니다. 로봇은 지도 위를 일분에 한 칸씩 상하좌우로 이동할 수 있습니다. 로봇의 위치와 목표 지점이 함께 주어질 경우, 로봇이 목표 지점까지 도달하는 데 걸리는 최소 시간을 리턴해야 합니다.

 

입출력 예시

let room = [
  [0, 0, 0, 0, 0, 0],
  [0, 1, 1, 0, 1, 0],
  [0, 1, 0, 0, 0, 0],
  [0, 0, 1, 1, 1, 0],
  [1, 0, 0, 0, 0, 0],
];
let src = [4, 2];
let dst = [2, 2];
let output = robotPath(room, src, dst);
console.log(output); // --> 8

 

!! 앞에서 햇던것과 다른것은? 2차원배열이다. 불린이아닌 count가 필요하다

2차원배열의 유효성검사?체크리스트? 만들때 잘살펴봐야한다. 

 

BFS 준비물 : QUE, WHILE, 유효성검사(valid나 체크리스트),

이번에 필요한건 ? => 변수 COUNT!!! 

 

1. Que를 만든다. 초기값 시작값 ? : src를 넣고시작

 

let que = [[...src,1]] // 여기서 1은 카운트값이다. 첫번째부터 1을 넣고 시작.

 

**카운트를 할때는 0일지 1인지 판단하는것이 중요하다.

 

2. visited 를 만든다. 

 

3.  visited를 만들었으니 넣어주자

visited[src[0]][src[1]] = 1

 

4. 상하앞뒤? 이거나오면 걍 국룰처럼 direction만드는거 외우자. (외웟으니 패스)

 

5. while문 돌리고

 

6. shift()한값을 que에 올려야하고 이걸로 계속  목표지점에 가까워지게 시도를 해야한다. 

let result = que.shift()

let [y,x,count] = result

 

7. for문 돌려!!

nexty nextx <= 원래있던거에서 상하좌우 넣어줘야된다. dir[i][0] dir[i][1] 이말인즉슨  direction안에있는 [-1,0]인 위로이동 좌표값을 넣어주기위해서  row col이 변하는걸 담아준다느것. <= 이렇게 dir.length만큼도니까 위아래오른쪽 왼쪽 다 검사하게된다.

 

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

마지막에 다다른값 dst[0]dst[1]에 다다르면 끝나야하니까 그때 카운트가 필요해서 result[2]

 

9. 이동이되면 이동한값 count+1을 담아줘야한다

 

const robotPath = function (room, src, dst) {
  // TODO: 여기에 코드를 작성합니다.
  // bfs <= 유효성검사. que. while. for문. 변수 카운트
  let que = [[...src,1]]
  let visited = new Array(room.length).fill(0).map(()=>Array())
  visited[src[0]][src[1]] = 1
  let dir = [
    [-1,0],
    [1,0],
    [0,-1],
    [0,1]
  ]
  while(que.length>0){
     let result= que.shift();  
    let [y, x, count] = result;
    for(let i=0; i<dir.length; i++){
      let ny = y + dir[i][0]
      let nx = x + dir[i][1]
      if(ny === dst[0] && nx === dst[1]) return result[2];
      if(ny<0 || nx<0 || ny>room.length-1 || nx>room[0].length-1) continue
      if(room[ny][nx] === 1) continue
      if(visited[ny][nx])continue
      visited[ny][nx] =1
      que.push([ny,nx,count+1])
      
    }
  }
};

 

---

 

그럼이제 DFS를 사용하여 연습해보자.