robotPath.js

어렵다..

문제설명 - robotPath

1. 주어진 n x n 사이즈의 board에 왼쪽 상단에 로봇이 위치한다
2. 그 로봇이 오른쪽 하단위치에 도착할수있는 경로의 경우의수를 계산하는 문제이다
3. 단, 같은 지점에 두번 방문할 수 없다

어떻게 풀어야하는지 도무지 감이 오지않아 구글에 검색해보았다. 검색하여 알아낸 코드는 아래와 같다

function makeBoard(n) {
  var board = [];
  for (var i = 0; i < n; i++) {
    board.push([]);
    for (var j = 0; j < n; j++) {
      board[i].push(false);
    }
  }
  board.togglePiece = function(i, j) {
    this[i][j] = !this[i][j];
  };
  board.hasBeenVisited = function(i, j) {
    return !!this[i][j];
  };
  return board;
}

function robotPaths(n) {
  var pathCount = 0;
  var board = makeBoard(n);

  function pathCounter(x, y) {
    // 경우의수 카운팅
    if (x === n - 1 && y === n - 1) {
      pathCount++;
      return;
    }

    if (x < 0 || y < 0 || x >= n || y >= n) {
      // 길이 없음
      return;
    }

    if (board.hasBeenVisited(x, y)) {
      // 방문했던 지점
      return;
    }

    board.togglePiece(x, y);
    console.log("board ? ", board);
    pathCounter(x, y + 1); // right
    pathCounter(x + 1, y); // bottom
    pathCounter(x, y - 1); // left
    pathCounter(x - 1, y); // top
    board.togglePiece(x, y);
    console.log("board ? ", board);
  }

  pathCounter(0, 0);

  return pathCount;
}

robotPaths(2);

이해한 내용 그림으로 정리

메모

• 하루에 2시간정도 알고리즘 풀어보기
  • 알고리즘 어렵다고 겁부터 내지말고 즐기자
  • 텅키코드, 스파게티코드 NO!!!!!
  • 쪼개서 생각하기
  • 변수별로 나눈다
  • 기능별로 함수를 나눈다
  • 나눈 함수를 상황에 맞게 돌린다
  • 결론, 함수를 잘 나눠야(쪼개야)한다
• 스프린트 내용이 이해되지 않는다면?
  - 구글에 스프린트관련 듀토리얼들을 따라해보고 어느정도 이해를 한 후에 스프린트에 들어간다

참고글

https://repl.it/@jordanbishop/SOLVEDrobotPaths
http://rvbsanjose.github.io/robot-paths/
https://www.youtube.com/watch?v=qJPYTIojBs0