[Codewars] Path Finder #1: can you reach the exit? (4 kyu) / JavaScript

https://www.codewars.com/kata/5765870e190b1472ec0022a2

Codewars - Achieve mastery through coding practice and developer mentorship

 

DESCRIPTION:

Task

You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return true if you can reach position [N-1, N-1] or false otherwise.

• Empty positions are marked ..
• Walls are marked W.
• Start and exit positions are empty in all test cases.

 

Path Finder Series:

• #1: can you reach the exit?
• #2: shortest path
• #3: the Alpinist
• #4: where are you?
• #5: there's someone here

 

---

설명:

작업

당신은 미로 NxN의 [0, 0] 위치에 있고 네 기본 방향(즉, 북쪽, 동쪽, 남쪽, 서쪽) 중 하나만 이동할 수 있습니다. 만약 당신이 [N-1, N-1]에 도달할 수 있으면 true를 그렇지 않다면 false를 반환하세요.

 

• 빈 위치는 .으로 표시됩니다.
• 벽은 W으로 표시됩니다.
• 모든 테스트 케이스에서 시작과 끝 위치는 비어있습니다.

 

경로 찾기 시리즈:

• #1: can you reach the exit?
• #2: shortest path
• #3: the Alpinist
• #4: where are you?
• #5: there's someone here

 

풀이

BFS로 풀었다. 시작점부터 상하좌우를 하나씩 확인해 범위를 벗어나지 않고 벽이 아니고 방문한 적이 없으면 그 위치를 방문했다고 체크해주고 queue에 넣는다. 다시 queue에 있는 위치를 대상으로 queue가 빌 때까지 같은 작업을 수행해준다. 그리고 모든 과정이 끝났을 때 [n - 1][n - 1]의 위치가 방문한 상태라면 true를 그렇지 않다면 false를 반환했다.

 

코드

function pathFinder(maze){
  maze = maze.split('\n').map(el => el.split(''));
  const n = maze.length;
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0 , -1, 1];
  let visited = Array.from(new Array(n), () => Array(n).fill(0));
  let queue = [];
  queue.push([0, 0]);
  visited[0][0] = 1;
  let num = 0
  while(num < queue.length){
    const [x, y] = queue[num];
    for(let i = 0; i < 4; i++){
      const xPos = x + dx[i];
      const yPos = y + dy[i];
      
      if(xPos < 0 || yPos < 0 || xPos >= n || yPos >= n) continue;
      if(maze[xPos][yPos] === 'W' || visited[xPos][yPos] === 1) continue;
      visited[xPos][yPos] = 1;
      queue.push([xPos, yPos]);
    }
    num++;
  }
  if(visited[n - 1][n - 1] !== 1) return false;
  return true;
}