[CodeKata] 프로그래머스(Lv3) : 사라지는 발판

🥋 Oooth More!! (Level 3) 

 

 

 

🧮 풀이

DFS를 적용해야한다고 생각은 했지만, A와 B가 최적의 경로로 이동하는것을 어떻게 반영할지에 대해 감이 잡히질 않았다.

(완전탐색을 통해 해결해야 한다)

 

 

 

🖇 리뷰

위에서 언급했듯, 완전탐색을 통해 A와 B가 모든 경로를 우선 방문한다.

탐색하면서 A 또는 B는 각자 이기거나 질 수 있는 사람인데, 이길수 있는 사람은 최소로, 질 수 있는 사람은 최대로 이동경로를 이동하려한다.

const solution = (board, aloc, bloc) => {
  const dx = [0, 0, 1, -1]
  const dy = [1, -1, 0, 0]

  const yMax = board.length
  const xMax = board[0].length

  const dfs = (aLoc, bLoc, turn, cnt) => {
    if ((turn === 0 && board[aLoc[0]][aLoc[1]] === 0) || (turn === 1 && board[bLoc[0]][bLoc[1]] === 0)) return {win: false, cnt: cnt}
    let win = Infinity
    let lose = 0

    const typedLoc = turn === 0 ? aLoc : bLoc
    board[typedLoc[0]][typedLoc[1]] = 0

    for (let idx = 0; idx < 4; idx++) {
      const nextLoc = [typedLoc[0] + dx[idx], typedLoc[1] + dy[idx]]
      if ((nextLoc[0] < 0 || nextLoc[0] >= yMax || nextLoc[1] < 0 || nextLoc[1] >= xMax) || !board[nextLoc[0]][nextLoc[1]]) continue
      const check = turn === 0 ? dfs(nextLoc, bLoc, 1 - turn, cnt + 1) : dfs(aLoc, nextLoc, 1 - turn, cnt + 1)
      if (check.win === false) win = Math.min(win, check.cnt)
      else lose = Math.max(lose, check.cnt)
    }

    board[typedLoc[0]][typedLoc[1]] = 1
    if (win === Infinity && lose === 0) return {win: false, cnt}
    else if (win !== Infinity) return {win: true, cnt: win}
    else return {win: false, cnt: lose}
  }

  return dfs(aloc, bloc, 0, 0).cnt
}

• dx, dy는 상하좌우 체크, yMax, xMax는 다음 이동경로가 board 우측 혹은 아래로 넘어가는지 체크하기 위한 값이다.
• dfs() 함수는 aLoc(a의 위치), bLoc(b의 위치), turn(a 차례면 0, b 차례면 1), cnt(이동횟수) 4개 인자를 받는다.
• A 혹은 B가 각 차례일 때 현재 위치의 board값이 0이면 더 이상 이동할 곳이 없는 것이다. 이 땐 지는 경우이며, cnt를 반환한다.
• 아니면, win과 lose를 각각 Infinity, 0으로 설정한다. 승자는 최소경로로 이동하기에 Math.min(), 패자는 최대경로로 이동하기에 Math.max() 로 비교하기 때문이다.
• typedLoc은 현재 turn의 Loc이다. 우선, board의 typedLoc 좌표를 우선 0으로 변경해서 다음 이동을 막는다.
• 다음으로, dx, dy를 순회해서 상하좌우 이동좌표인 nextLoc을 계산한다. 이 좌표가 board를 벗어나거나 0인 경우, 반복문을 continue로 스킵한다.
• check는 다음 DFS를 진행한 후의 결과로, turn이 0이면 A를, 아니면 B를 nextLoc을 넣고, turn을 바꾸고 cnt는 1을 더한다.
• check의 win이 false면 지금은 이기는 경우이므로 win 값을, true면 지는 경우이므로 lose 값을 갱신한다.
• 탐색이 마무리되면 board의 typedLoc 좌표를 다시 1로 돌린다.(옆 탐색을 위해)
  • 첫 if는 모든 이동이 불가한 경우이다.(값이 그대로) 이 때 역시 지는 경우로, cnt를 반환한다.
  • 다음 else if는 win이 바뀐 승리한 경우다. 이 땐, win은 true, cnt에는 win 값을 넣어준다.
  • 마지막 else는 lose가 바뀐 패배한 경우다. 이 땐, win은 false, cnt는 lose 값을 넣어준다.

 

 

* 다른 풀이

function solution(board, aloc, bloc) {
  const row_len = board.length;
  const col_len = board[0].length;
  const dir = [[1,0],[-1,0],[0,1],[0,-1]];
  let OOB = (x,y)=>{return x<0 || x>=row_len || y < 0 || y >= col_len;}
  let DFS = (curLoc,nextLoc)=>{
    if(!board[curLoc[0]][curLoc[1]]){return 0;}
    let ret = 0;
    board[curLoc[0]][curLoc[1]]=0;
    for(let i = 0; i < 4; i++){
      let nx = curLoc[0]+dir[i][0];
      let ny = curLoc[1]+dir[i][1];
      if(OOB(nx,ny)||!board[nx][ny]){continue;}
      let count = DFS(nextLoc,[nx,ny])+1;

      if(ret%2===0&&count%2===1){ret = count;}
      else if(ret%2===0&&count%2===0){ret = Math.max(ret,count);}
      else if(ret%2===1&&count%2===1){ret = Math.min(ret,count);}
    }
    board[curLoc[0]][curLoc[1]]=1;
    return ret;
  }
  return DFS(aloc,bloc);
}

위 풀이가 좀 더 깔끔하지만, count / 최대값 / 최소값을 넣는 조건 자체가 확실히 이해가 안되서 좀 더 직관적인 풀이를 위에 적었다.