Programmers / Level 2 / 미로 탈출 / JS

문제 간단설명

1 x 1 크기의 칸들로 이루어진 직사각형 형태의 미로가 있다. 시작지점에서 도착지점까지 가야하는 최소거리를 구하면 된다. 그런데, 가야하는 통로중에 문이 있는데, 레버로 먼저 열어야 지나갈 수 있다.

 

따라서 시작지점 -> 레버 -> 도착지점 순으로 들려야 미로를 빠져나갈 수 있다.

 

위와 같이 이동한다고 했을 때, 최소시간을 구하면 된다. 만약 탈출할 수 없다면 -1을 반환하면 된다.

 

제한 사항

• 5 <= maps의 길이 <= 100
  • 5 <= maps[i]의 길이 <= 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재한다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있다.

 

실패 코드

function solution(maps) {
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    
    const START = 'S';
    const END = 'E';
    const LEVER = 'L';
    const PATH = 'O';
    const WALL = 'X';
    
    let distanceFromStartToLever = 0;
    let distanceFromLeverToEnd = 0;
    
    const length = maps.length;
    
    const isValid = (row, col) => {
        if(row < 0 || row >= length) {
            return false;
        }
        if(col < 0 || col >= length) {
            return false;
        }
        
        return true;
    }
    
    const getDistanceFromStartToLever = () => {
        const queue = [];
        const visited = Array.from({ length }, () => Array.from({ length }, () => false));
        
        for(let i=0; i<length; i++) {
            for(let j=0; j<length; j++) {
                if(maps[i][j] === START) {
                    queue.push([i, j, 0]);
                    visited[i][j] = true;
                } 
            }
        }
        
        while(queue.length > 0) {
            const [curRow, curCol, time] = queue.shift();
            
            if(maps[curRow][curCol] === LEVER) {
                return time;
            }
            
            for(let d=0; d<4; d++) {
                const nr = curRow + dr[d];
                const nc = curCol + dc[d];
                
                if(isValid(nr, nc) === false) {
                    continue;
                }
                if(visited[nr][nc] === true) {
                    continue;
                }
                if(maps[nr][nc] === WALL) {
                    continue;
                }
                
                visited[nr][nc] = true;
                queue.push([nr, nc, time + 1]);
            }
        }
    }
    
    const getDistanceFromLeverToEnd = () => {
        const queue = [];
        const visited = Array.from({ length }, () => Array.from({ length }, () => false));
        
        for(let i=0; i<length; i++) {
            for(let j=0; j<length; j++) {
                if(maps[i][j] === LEVER) {
                    queue.push([i, j, 0]);
                    visited[i][j] = true;
                } 
            }
        }
        
        while(queue.length > 0) {
            const [curRow, curCol, time] = queue.shift();
            
            if(maps[curRow][curCol] === END) {
                return time;
            }
            
            for(let d=0; d<4; d++) {
                const nr = curRow + dr[d];
                const nc = curCol + dc[d];
                
                if(isValid(nr, nc) === false) {
                    continue;
                }
                if(visited[nr][nc] === true) {
                    continue;
                }
                if(maps[nr][nc] === WALL) {
                    continue;
                }
                
                visited[nr][nc] = true;
                queue.push([nr, nc, time + 1]);
            }
        }
    }
    
    return getDistanceFromStartToLever() + getDistanceFromLeverToEnd() || -1;
}

 

위 코드는 몇 개의 테스트케이스를 통과하지 못했다. 그 이유는...

바보같이 문제를 잘못 읽었다... 미로가 당연히 정사각형이라고 생각하고 풀이를 했다. 행의 길이와 열의 길이를 따로 구해주어 문제를 풀어야한다.

 

로직적인 문제 외에도 위 코드를 보면 같은 로직의 BFS 함수가 2개 존재하는 것을 볼 수 있다.

물론 문제는 없지만, 모듈화해서 다음과 같이 문제점들을 수정해서 성공할 수 있었다.

 

성공 코드

function solution(maps) {
  const dr = [-1, 1, 0, 0];
  const dc = [0, 0, -1, 1];

  const START = 'S';
  const END = 'E';
  const LEVER = 'L';
  const PATH = 'O';
  const WALL = 'X';

  const totalRow = maps.length;
  const totalCol = maps[0].length;

  /**
   * 인자로 받은 행과 열이 유효한 위치인지 boolean 값으로 반환하는 함수이다.
   *
   * @param {number} row 행
   * @param {number} col 열
   * @returns 유효한 위치라면 true, 아니라면 false를 반환한다.
   */
  const isValid = (row, col) => {
    if (row < 0 || row >= totalRow) {
      return false;
    }
    if (col < 0 || col >= totalCol) {
      return false;
    }

    return true;
  };

  /**
   * BFS를 이용해 시작할 곳과 도착할 곳의 문자를 받아서 최소거리를 구하는 함수이다.
   *
   * @param {string} start 시작 문자
   * @param {string} end 도착 문자
   * @returns 다다를 수 없다면 -1, 다다를 수 있다면 최소거리를 반환한다.
   */
  const getDistance = (start, end) => {
    const queue = [];
    const visited = Array.from({ length: totalRow }, () =>
      Array.from({ length: totalCol }, () => false)
    );

    for (let i = 0; i < totalRow; i++) {
      for (let j = 0; j < totalCol; j++) {
        // 시작 위치를 queue에 넣어주고, 방문처리를 해준다.
        if (maps[i][j] === start) {
          queue.push([i, j, 0]);
          visited[i][j] = true;
        }
      }
    }

    while (queue.length > 0) {
      const [curRow, curCol, time] = queue.shift();

      if (maps[curRow][curCol] === end) {
        return time;
      }

      for (let d = 0; d < 4; d++) {
        const nr = curRow + dr[d];
        const nc = curCol + dc[d];

        // 유효하지 않다면 넘어간다.
        if (isValid(nr, nc) === false) {
          continue;
        }
        // 이미 방문했다면 넘어간다.
        if (visited[nr][nc] === true) {
          continue;
        }
        // 벽으로 막혀있다면 넘어간다.
        if (maps[nr][nc] === WALL) {
          continue;
        }

        visited[nr][nc] = true;
        queue.push([nr, nc, time + 1]);
      }
    }

    return -1;
  };

  const distanceFromStartToLever = getDistance(START, LEVER);
  const distanceFromLeverToEnd = getDistance(LEVER, END);

  // 시작지점에서 레버, 혹은 레버에서 도착지점까지 둘 중 하나라도 다다를 수 없다면 -1을 반환한다.
  if (distanceFromStartToLever === -1 || distanceFromLeverToEnd === -1) {
    return -1;
  }

  return distanceFromStartToLever + distanceFromLeverToEnd;
}