프로그래머스 : 블록 이동하기 - javascript (bfs)

## 문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

 

## 문제 풀이 힌트 

출제 의도: BFS에 대해 알고 있고, 이를 응용해(단순 암기가 아니라) 코드를 작성할 수 있는지 파악 

 

세팅 

1) 이차원 그래프 새로 생성하기

  - 좌표 자체가 1,1로 시작하고, n,n 을 구해야 하기 때문에 코드 편의성을 위해 n+2, n+2 그래프로 생성. 

  - 전체를 벽인 1로 세팅한 후, 주어진 board 값에 맞춰서 0인 값으로 다시 넣어준다. 

2) goal을 문자열로 설정할 것.

  - 이동하는 위치를 문자열로 비교할 것임. 

3)  Set 객체로 중복 확인 

  - 왼쪽과 오른쪽의 위치를 문자열로 저장 

 

함수 구현 

 1. 현재 위치에서 다음 이동이 가능한 경우를 구하는 함수 작성

- 상하좌우 : 4가지 경우 

- 회전 (대각선에 벽이 없어야함) : 4가지 경우

총 8가지 경우에서 가능한 위치를 return 해준다. 

 

2. 목표에 도착했는지 확인하는 함수 작성 

- 위 이동 가능한 함수에서 중복으로 가지 않게 set 객체 이용해서 queue에 push 

- 만약 좌표가 도착지랑 같다면 지금까지의 이동 거리 return 

 

다른 분의 코드를 보고, 내 언어로 작성을 해보았는데 난 에러가 났다. (남의 코드는 나한테 가독성이 안좋음) 

다른 분의 코드를 살며시 놓고 간다... 

내 코드가 정답이 됐을 때 슬쩍 코드를 변경하겠다. 

 

^^ 

## 정답 풀이 코드 

function solution (board) {
  // 지도의 크기를 저장합니다.
  const N = board.length;
  
  // 목표 위치를 문자열로 저장합니다.
  const goal = N + '' + N;
  
  // BFS 탐색을 위한 큐로, 초기에는 로봇의 시작 위치와 움직인 횟수(0)를 포함합니다.
  const queue = [ [ [1,1], [1,2], 0 ] ];
  
  // 방문한 위치를 기록하기 위한 Set입니다. 초기에는 로봇의 시작 위치가 포함됩니다.
  const visit = new Set(["1112"]);
  
   // 주어진 board 외곽에 벽(1)을 추가하여 생성된 새로운 보드입니다. 
   const new_board = new Array(N+2).fill().map(_ => new Array(N+2).fill(1));
   
   // 생성된 새 보드에 기존 데이터를 입힘(외곽 제외)
   for(let i = 0; i < N; i++) {
    for(let j = 0; j < N; j++) {
      new_board[i+1][j+1] = board[i][j];
    }
   }
   
   while(queue.length) { 
    // BFS 탐색을 수행하여 목표 위치에 도달할 때까지 반복적으로 실행됩니다.
    const [left, right, count] = queue.shift();
    
    if(left.join('') === goal || right.join('') === goal) return count;
    
    const nextPosition = getNextPosition(left, right, new_board);
    
    for(const next of nextPosition) {
      const [next_left, next_right] = next;
      const key = next_left.join('') + next_right.join('');
      
      // 방문기록이 없다면, 큐에 담고 방문기록에 추가
      if(!visit.has(key)) {
        queue.push([next_left, next_right, count+1]);
        visit.add(key);
      }
     }
   }
}

const getNextPosition = (left, right, board) => {
    // 현재 로봇의 각 부분(left와 right)에서 가능한 다음 위치들을 반환합니다.

    // 가능한 다음 위치들을 저장하기 위해 사용됩니다.
    const result=[];

    // 좌표 표현 용이성과 가독성 향상을 위해 사용됩니다. 
    const X=1,Y=0;

    // 상하좌우 이동 방향을 나타내며 각각 dy와 dx 값을 가집니다
    const moves=[[ -1 ,0 ],[ 1 ,0 ],[ 0 ,-1 ],[0 ,1]];

    for(const move of moves){
        // 상하좌우로 이동할 수 있는 경우를 확인하고 결과 배열에 추가합니다
        const dy=move[Y];
        const dx=move[X];
        const left_next=[left[Y]+dy,left[X]+dx];
        const right_next=[right[Y]+dy,right[X]+dx];

        if(board[left_next[Y]][left_next[X]]===0 && board[right_next[Y]][right_next[X]]===0){
            result.push([left_next,right_next]);
        }
    }

    // 회전 가능성 확인시 사용되는 값으로 양방향(-1과 1) 검사가 필요하기 때문입니다
    const rotate=[-1,1];

    if(left[Y] === right[Y]){
        // 로봇이 가로방향일 경우 세로방향으로 회전할 수 있는 경우를 확인하고 결과 배열에 추가합니다
        for(const dy of rotate){
            if(board[left[Y]+dy][left[X]] === 0 && board[right[Y]+dy][right[X]] === 0) {
                result.push([ left, [ left[Y]+dy, left[X] ] ]);
                result.push([ [ right[Y]+dy, right[X] ], right ]);
            }
        }
    } else {
        // 그렇지 않은 경우(즉, 로봇이 세로방향일 경우) 가로방향으로 회전할 수 있는 경우를 확인하고 결과 배열에 추가합니다
        for(const dx of rotate){
          if(board[left[Y]][left[X]+dx] === 0 && board[right[Y]][right[X]+dx] === 0) {
            result.push([ [left[Y], left[X]+dx ], left ]);
            result.push([ right, [ right[Y], right[X]+dx ] ]);
          }
        }
    }

    return result;
}

 

## only 풀이 코드 

function solution(board) {
  const N = board.length;
  const goal = N + '' + N;
  const queue = [ [[1,1], [1,2], 0] ];
  const visit = new Set(["1112"]);
  const new_board = new Array(N+2).fill().map(_ => new Array(N+2).fill(1));
  
  for(let i = 0; i < N; i++) {
    for(let j = 0; j < N; j++) {
      new_board[i+1][j+1] = board[i][j];
    }
  }

  while(queue.length) { 
    const [left, right, count] = queue.shift();
    if(left.join('') === goal || right.join('') === goal) return count;
    const nextPosition = getNextPosition(left, right, new_board);
    for(const next of nextPosition) {
      const [next_left, next_right] = next;
      const key = next_left.join('') + next_right.join('');
      if(!visit.has(key)) {
        queue.push([next_left, next_right, count+1]);
        visit.add(key);
      }
    }
  }
}

const getNextPosition = (left, right, board) => {
  const result = [];
  const X = 1, Y = 0;
  const moves = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  for(const move of moves){
    const dy = move[Y];
    const dx = move[X];
    const left_next = [left[Y]+dy, left[X]+dx];
    const right_next = [right[Y]+dy, right[X]+dx];

    if(board[left_next[Y]][left_next[X]] === 0 && board[right_next[Y]][right_next[X]] === 0){
      result.push([left_next, right_next]);
    }
  }

  const rotate = [-1, 1];
  if(left[Y] === right[Y]){
    for(const dy of rotate){
      if(board[left[Y]+dy][left[X]] === 0 && board[right[Y]+dy][right[X]] === 0) {
        result.push([left, [left[Y]+dy, left[X]]]);
        result.push([[right[Y]+dy, right[X]], right]);
      }
    }
  } else {
    for(const dx of rotate){
      if(board[left[Y]][left[X]+dx] === 0 && board[right[Y]][right[X]+dx] === 0) {
        result.push([[left[Y], left[X]+dx], left]);
        result.push([right, [right[Y], right[X]+dx]]);
      }
    }
  }

  return result;
}

## 나의 틀린 풀이 

function solution(board) {
    const n = board.length; 
    
    const graph = Array.from({length: n+1}).map(() => new Array(n+2).fill(1))
    for(let i=0; i<n; i++){
        for(let j=0; j<n; j++){
            graph[i+1][j+1] = board[i][j]
        }
    }
    const queue = [[[1,1], [1,2], 0]]; 
    const goal = `${n}${n}`; 
    const set = new Set(['1112' ]); 
    //여기는 중복을 체크하기 
    while(queue.length){
        let [left, right, d] = queue.shift(); 
        if(left.join('') === goal|| right.join('') === goal) return d; 
       const nexts = getNextPosition(left, right, board); 
        for(let next of nexts){
            let next_left = next[0]; 
            let next_right = next[1]; 
            let candi = next_left.join('')+ ''+ next_right.join(''); 
            if(!set.has(candi)){
                set.add(candi); 
                queue.push([next, d+1]); 
            }
        }
    }
}

//이동할 수 있는 위치 return 
//상하좌우 
//회전 
const getNextPosition = (left, right, graph) => {
  const results = []; 
  const dx = [-1,1,0,0]; 
  const dy = [0,0,-1,1];
    for(let i=0; i<4; i++){
        let left_next = [left[0]+dy, left[1]+dx];
        let right_next = [right[0]+dy, right[1]+dx];
        if(!left_next.includes(0) && !right_next.includes(0)){
            results.push([left_next, right_next])
        }
    }; 
    //왼쪽이 축일 때, 오른쪽이 축일 때 이동 
    //만약 그 대각선이 0일 때 push 

        //왼쪽 위, 아래 값이 0일 때 왼쪽 회전 가능 
        //오른쪽 위, 아래 값이 0일 때 오른쪽 회전 가능
        if(graph[left[0] + (-1)][left[1]] === 0 && graph[left[0] -1 ][left[1]+1] === 0){
            results.push([[left[0] -1 , left[1]+1], right])
        }else if(graph[left[0] + (1)][left[1]] === 0 && graph[left[0] + 1][left[1] + 1] === 0){
            results.push([[left[0] + 1,left[1] + 1], right])
        }else if(graph[right[0] + -1][right[1]] === 0 && graph[right[0] -1][right[1] -1] === 0){
            results.push([left, [right[0] -1,right[1] -1]])
        }else if(graph[right[0] + 1][right[1]] === 0 && graph[right[0] +1][right[1] -1] === 0){
            results.push([left, [right[0] +1,right[1] -1]])
    }
    return results ; 
}
//새로운 그래프 생성 
//-1로 채우기 
//-0인 것 채우기 
//중복 체크하는 set 객체 
//