Portfolio

문제

풀이

재영

BFS, DFS 완전탐색을 해야 한다.

array를 만들었을 때 테두리를 정확히 산정해야 돼요.

코너일 때 어떻게 해결할 것이냐.


class Queue {
  constructor(arr) {
    this.queue = arr ? arr : [];
    this.front = 0;
    this.rear = arr ? arr.length - 1 : 0;
    this.length = arr ? arr.length : 0;
  }

  enqueue(val) {
    this.queue.push(val);

    this.rear += 1;
    this.length += 1;
  }

  dequeue() {
    const value = this.queue[this.front];

    delete this.queue[this.front];

    this.front += 1;
    this.length -= 1;

    return value;
  }
}

const directions = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];

const makeBoard = (rectangle) => {
  const board = Array.from({ length: 102 }, () => new Array(102).fill(0)); // 2배

  rectangle.forEach((nowRectangle) => {
    const startX = nowRectangle[0] * 2;
    const startY = nowRectangle[1] * 2;
    const endX = nowRectangle[2] * 2;
    const endY = nowRectangle[3] * 2;

    for (let i = startX; i <= endX; i += 1) {
      for (let j = startY; j <= endY; j += 1) {
        board[i][j] = 1;
      }
    }
  });

  return board;
};

const bfs = (queue, board, itemX, itemY) => {
  const isBoarder = (x, y) => { // 저는 다 1로 매김 -> 8방향을 체크
    const allDirections = [[1, 1], [-1, -1], [1, -1], [-1, 1], ...directions];

    for (let i = 0; i < 8; i += 1) {
      const [dx, dy] = allDirections[i];
      const nx = x + dx;
      const ny = y + dy;

      if (nx === 1 || ny === 1 || nx === 101 || ny === 101) return true;
      if (board[nx][ny] === 0) {
        return true;
      }
    }

    return false;
  };

  while (queue.length) {
    const [count, x, y] = queue.dequeue();
    board[x][y] = -1;

    if (x === itemX && y === itemY) return parseInt(count / 2);

    for (let i = 0; i < 4; i += 1) {
      const [dx, dy] = directions[i];
      const nx = x + dx;
      const ny = y + dy;

      if (
        nx >= 0 &&
        ny >= 0 &&
        nx <= 100 &&
        ny <= 100 &&
        board[nx][ny] === 1 &&
        isBoarder(nx, ny)
      ) {
        board[nx][ny] = -1;
        queue.enqueue([count + 1, nx, ny]);
      }
    }
  }
};

const solution = (rectangle, characterX, characterY, itemX, itemY) => {
  const refinedCharacterX = characterX * 2;
  const refinedCharacterY = characterY * 2;
  const refinedItemX = itemX * 2;
  const refinedItemY = itemY * 2;

  const board = makeBoard(rectangle);
  board[refinedCharacterX][refinedCharacterY] = -1; // 방문 여부 -1

  const queue = new Queue();
  queue.enqueue([0, refinedCharacterX, refinedCharacterY]); //  JSON.parse(JSON.stringify(board))

  return bfs(queue, board, refinedItemX, refinedItemY);
};

은찬


function solution(rectangle, characterX, characterY, itemX, itemY) {
    let answer = 0;
    const map = Array.from({length: 200}, () => Array(200).fill(0));
    const visited = Array.from({length: 200}, () => Array(200).fill(false));
    const direct = [[-1, 0], [0, 1], [1, 0], [0, -1], [-1, -1], [-1, 1], [1, 1], [1, -1]];
    const queue = [];
    
    const checkRange = (x, y) => x > 0 && x < 200 && y > 0 && y < 200;
    
    const isInner = (x, y) => {
        for(let i = 0; i < 8; i++){
            const nx = x + direct[i][0];
            const ny = y + direct[i][1];
            
            if(!map[nx][ny]){
                return false;
            }
        }
        
        return true;
    }
    
    for(let i = 0; i < rectangle.length; i++){
        const [x1, y1, x2, y2] = rectangle[i];
        
        for(let x = x1 * 2; x <= x2 * 2; x++){
            for(let y = y1 * 2; y <= y2 * 2; y++){
                map[x][y] = 1;
            }
        }
    }
    
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;
    
    queue.push([characterX, characterY, 0]);
    visited[characterX][characterY] = true;
    
    while(queue.length){
        const [x, y, count] = queue.shift();
        
        if(x === itemX && y === itemY){
            return Math.floor(count / 2);
        }
        
        for(let i = 0; i < 4; i++){
            const nx = x + direct[i][0];
            const ny = y + direct[i][1];
            
            if(checkRange(nx, ny) && !isInner(nx, ny) && map[nx][ny] === 1 && !visited[nx][ny]){                
                queue.push([nx, ny, count + 1]);
                visited[nx][ny] = true;
            }
        }
    }
    
    return answer;
}

효성


function solution(rectangle, characterX, characterY, itemX, itemY) {
    let board = Array.from(Array(103), () => Array(103).fill(0));
    
    const doubleRec = rectangle.map(pos1 => pos1.map(pos2 => pos2 * 2));
    
    doubleRec.forEach(([x1, y1, x2, y2]) => {
        for(let i = x1; i <= x2; i++) {
            for(let j = y1; j <= y2; j++) {
                if(i === x1 || i === x2 || j === y1 || j === y2) {
                    if (board[i][j] === 1) {
                        continue;
                    } else {
                        board[i][j] += 1; 
                    }
                }
                else {
                    board[i][j] += 2;
                }
            }
        }
    });
    
	const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;
    
    const queue = [[characterX, characterY, 0]];
    board[characterX][characterY] += 2;
	
    while(queue.length) {
        const [x, y, cnt] = queue.shift();
        
        if(x === itemX && y === itemY) {
            return cnt / 2;
        }
        
        for(let i = 0; i < 4; i++) {
            const [nx, ny] = [x + dx[i], y + dy[i]];
            if(nx >= 0 && nx < 101 && ny >= 0 && ny < 101) {
                if(board[nx][ny] === 1) {
                    board[nx][ny] += 2;
                    queue.push([nx, ny, cnt + 1]);
                }
            }
        }
    }
}

아이템 줍기

문제

풀이