알고리즘 문제 풀이(프로그래머스 - 블록 이동하기)

프로그래머스 LEVEL 3(블록 이동하기)

• 사용 언어 : javascript

• 해결 날짜 : 2023-05-19

• 해결 방법 :

  • bfs를 활용해 문제 해결
    • 방문 여부를 체크하기 위해 Set 선언, ‘x1y1x2y2’의 String 형태로 삽입
    • board 1씩 확장
    • bfs 수행
      • 이미 방문했다면 continue로 시간 절약
      • 방문하지 않았다면 방문 체크 후
        • 상, 하, 좌, 우 이동
        • 축1을 기준으로 시계 방향, 반시계 방향 회전
        • 축2를 기준으로 시계 방향, 반시계 방향 회전
        • 했을 때 벽이 아니거나 board를 넘어가지 않는다면 q에 삽입
      • 마지막 N, N에 도달했을 때 time 반환

• 회고 :

  • 처음에 작성한 코드

    function solution(board) {
      const N = board.length;
    
      const moves = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0],
      ];
      const rotates = [1, -1];
    
      const visited = new Set();
    
      const q = [[[0, 0], [1, 0], 0]];
    
      while (q.length) {
        const [axis1, axis2, time] = q.shift();
        const [x1, y1] = axis1,
          [x2, y2] = axis2;
    
        if (visited.has(`${x1}${y1}${x2}${y2}`)) {
          continue;
        }
    
        visited.add(`${x1}${y1}${x2}${y2}`);
    
        if ((x1 === N - 1 && y1 === N - 1) || (x2 === N - 1 && y2 === N - 1)) {
          return time;
        }
    
        moves.forEach(([mx, my]) => {
          const [nx1, ny1, nx2, ny2] = [x1 + mx, y1 + my, x2 + mx, y2 + my];
    
          if (
            nx1 < 0 ||
            ny1 < 0 ||
            nx2 < 0 ||
            ny2 < 0 ||
            nx1 >= N ||
            ny1 >= N ||
            nx2 >= N ||
            ny2 >= N ||
            board[ny1][nx1] === 1 ||
            board[ny2][nx2] === 1 ||
            visited.has(`${nx1}${ny1}${nx2}${ny2}`)
          ) {
            return;
          }
    
          q.push([[nx1, ny1], [nx2, ny2], time + 1]);
        });
    
        rotates.forEach((rotate) => {
          if (y1 === y2) {
            const ny = y1 + rotate;
    
            if (
              ny < 0 ||
              ny >= N ||
              board[ny][x1] === 1 ||
              board[ny][x2] === 1 ||
              visited.has(`${x1}${ny}${x2}${ny}`)
            ) {
              return;
            }
    
            q.push([[x1, y1], [x1, ny], time + 1]);
            q.push([[x2, y2], [x2, ny], time + 1]);
          } else if (x1 === x2) {
            const nx = x1 + rotate;
    
            if (
              nx < 0 ||
              nx >= N ||
              board[y1][nx] === 1 ||
              board[y2][nx] === 1 ||
              visited.has(`${nx}${y1}${nx}${y2}`)
            ) {
              return;
            }
    
            q.push([[x1, y1], [nx, y1], time + 1]);
            q.push([[x2, y2], [nx, y2], time + 1]);
          }
        });
      }
    }
    

  • 테스트 케이스 8, 14 두 개를 통과하지 못했다..

    

  • 이유는 모르겠으나 board에 패딩을 1씩 주고, board에 접근할 때 x, y 위치를 바꿨더니 통과했다.. 아시는 분 알려주세요..ㅠㅠ

    

• 코드

  function solution(board) {
    const N = board.length;
  
    const moves = [
      [0, 1],
      [1, 0],
      [0, -1],
      [-1, 0],
    ];
    const rotates = [1, -1];
  
    const visited = new Set();
    const extendedBoard = Array.from({ length: N + 2 }, () =>
      Array.from({ length: N + 2 }, () => 1),
    );
  
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        extendedBoard[i + 1][j + 1] = board[i][j];
      }
    }
  
    const q = [[[1, 1], [1, 2], 0]];
  
    while (q.length) {
      const [axis1, axis2, time] = q.shift();
      const [x1, y1] = axis1,
        [x2, y2] = axis2;
  
      if (visited.has(`${x1}${y1}${x2}${y2}`)) {
        continue;
      }
  
      visited.add(`${x1}${y1}${x2}${y2}`);
  
      if ((x1 === N && y1 === N) || (x2 === N && y2 === N)) {
        return time;
      }
  
      moves.forEach(([mx, my]) => {
        const [nx1, ny1, nx2, ny2] = [x1 + mx, y1 + my, x2 + mx, y2 + my];
  
        if (extendedBoard[nx1][ny1] === 1 || extendedBoard[nx2][ny2] === 1) {
          return;
        }
  
        q.push([[nx1, ny1], [nx2, ny2], time + 1]);
      });
  
      rotates.forEach((rotate) => {
        if (y1 === y2) {
          const ny = y1 + rotate;
  
          if (extendedBoard[x1][ny] === 1 || extendedBoard[x2][ny] === 1) {
            return;
          }
  
          q.push([[x1, y1], [x1, ny], time + 1]);
          q.push([[x2, ny], [x2, y2], time + 1]);
        } else if (x1 === x2) {
          const nx = x1 + rotate;
  
          if (extendedBoard[nx][y1] === 1 || extendedBoard[nx][y2] === 1) {
            return;
          }
  
          q.push([[x1, y1], [nx, y1], time + 1]);
          q.push([[nx, y2], [x2, y2], time + 1]);
        }
      });
    }
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges