Portfolio

📑 문제

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

✏️ 풀이

재영

일단 이 문제를 보자마자, DFS보다는 BFS가 훨씬 더 효율적이고 정확한 답이 나올 거라 생각했어요. 최소 이동을 구하는 문제였기 때문입니다.

따라서 일단 크게 함수를 나눴어요.

main: 인풋을 받고 결과를 리턴시키는 메인 함수

getMinimizedMovement: 각 상황마다의 최소 이동을 구해주는 함수

getMinimizedMovement의 경우, BFS에 맞춰 큐와 visited를 구현해줘요.

그 다음부터는 방문했을 때와 하지 않았을 때에 맞춰서, 조건 처리를 해주면 결과가 나옵니다!


const fs = require('fs');
const input = fs.readFileSync("나이트의이동.txt").toString().trim().split("\n");

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(data) {
    this.queue[this.rear] = data;
    this.rear += 1;
  }
  dequeue() {
    const popleft = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return popleft;
  }
  size() {
    return this.rear - this.front;
  }
}

const main = input => {
  let result = [];
  let inputIdx = 0;
  const cnt = input[inputIdx++];

  for (let i = 0; i < cnt; i++) {
    const boardSize = parseInt(input[inputIdx++]);
    const startXY = input[inputIdx++].trim().split(' ').map(val => parseInt(val));
    const destinationXY = input[inputIdx++].trim().split(' ').map(val => parseInt(val));
    result = [
        ...result, 
        getMinimizedMovement(boardSize, startXY, destinationXY)
    ]
  }
  result.forEach((minimizedMovement) => console.log(minimizedMovement));
}

const getMinimizedMovement = (boardSize, startXY, destinationXY) => {
  const visited = Array.from(new Array(boardSize), () => new Array(boardSize).fill(false));

  const [startX, startY] = startXY;
  const [destinationX, destinationY] = destinationXY;
  const nextDirections = [
    [2, 1], 
    [2, -1], 
    [1, 2], 
    [1, -2], 
    [-1, 2], 
    [-1, -2], 
    [-2, 1], 
    [-2, -1]
  ]

  const queue = new Queue();
  queue.enqueue([startX, startY, 0]);

  while (queue.size()) {
    const [x, y, moveCnt] = queue.dequeue();
    if (destinationX === x && destinationY === y) {
      return moveCnt;
    }
    nextDirections.forEach(([nextX, nextY]) => {
      const nx = x + nextX;
      const ny = y + nextY;
      if (nx >= 0 && ny >= 0 && nx < boardSize && ny < boardSize && !visited[nx][ny]) {
        visited[nx][ny] = true;
        queue.enqueue([nx, ny, moveCnt + 1]);
      }
    })
  }
}

main(input);

효성


from collections import deque

dx=[1,2,2,1,-1,-2,-2,-1]
dy=[2,1,-1,-2,-2,-1,1,2]

n = int(input())

for i in range(n):
    l = int(input())
    graph =[]
    for i in range(l):
        graph.append([0]*l)
        queue = deque()
        x,y = map(int, input().split())
        w,z = map(int, input().split())
        queue.append((x,y))
        while queue:
            x,y=queue.popleft()
            if x==w and y==z:
                break
            for i in range(8):
                nx = x+dx[i]
                ny = y+dy[i]
                if nx<0 or ny<0 or nx>=l or ny>=l:
                    continue
                if graph[nx,ny] == 0:
                    graph[nx][ny] = graph[x][y]+1
                    queue.append((nx,ny))
        print(graph[w][z])

은찬


const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split("\n");

const tc = +input[0];
const directX = [-1, -2, -2, -1, 1, 2, 2, 1];
const directY = [-2, -1, 1, 2, -2, -1, 1, 2];

const checkRange = (x, y, length) => (x >= 0 && x < length && y >= 0 && y < length ? true : false);

const moveNight = () => {
    for (let repeat = 0; repeat < tc; repeat++) {
        const index = repeat * 3;
        const night = input[index + 2].split(" ");
        const target = input[index + 3].split(" ");

        const length = +input[index + 1];
        const nightX = +night[0];
        const nightY = +night[1];
        const targetX = +target[0];
        const targetY = +target[1];
        let answer = 0;

        const visited = Array.from({ length }, () => Array(length).fill(false));
        const queue = [[nightX, nightY]];

        visited[nightX][nightY] = true;

        while (queue.length) {
            let size = queue.length;
            let isBreak = false;

            while (size--) {
                const [currentX, currentY] = queue[0];

                queue.shift();

                if (currentX === targetX && currentY === targetY) {
                    console.log(answer);
                    isBreak = true;
                    break;
                }

                for (let i = 0; i < 8; i++) {
                    const nx = currentX + directX[i];
                    const ny = currentY + directY[i];

                    if (checkRange(nx, ny, length) && !visited[nx][ny]) {
                        queue.push([nx, ny]);
                        visited[nx][ny] = true;
                    }
                }
            }

            if (isBreak) {
                break;
            }

            answer++;
        }
    }
};

moveNight();

현석


function solution(data) {
  const [size, start, end] = data;
  const [startRow, startCol] = start;
 
  const [endRow, endCol] = end;
  const visited = Array.from({length: size[0]}, () =>new Array(size[0]).fill(false));
  const queue = [[startRow, startCol, 0]];
  let result = 0;
  
  while(queue.length) {
    const [currRow, currCol, countMove] = queue.shift();
    
    if (visited[currRow][currCol]) continue;
    visited[currRow][currCol] = true;
   
    
    if (currRow === endRow && currCol === endCol) {
      result = countMove;
      break;
    }

    if (currRow - 2 >= 0 && currCol - 1 >= 0) {
      queue.push([currRow-2, currCol - 1, countMove+1]);  
    }

    if (currRow - 2 >= 0 && currCol + 1 < size) {
      queue.push([currRow-2, currCol + 1, countMove+1]);  
    }

    if (currRow + 2 < size && currCol - 1 >= 0) {
      queue.push([currRow+2, currCol -1, countMove+1]);  
    }

    if (currRow + 2 < size && currCol + 1 < size) {
      queue.push([currRow+2, currCol +1, countMove+1]);  
    }

    if (currRow - 1 >= 0 && currCol - 2 >= 0) {
      queue.push([currRow-1, currCol - 2, countMove+1]);  
    }

    if (currRow - 1 >= 0 && currCol + 2 < size) {
      queue.push([currRow-1, currCol + 2, countMove+1]);  
    }

    if (currRow + 1 < size && currCol - 2 >= 0) {
      queue.push([currRow+1, currCol -2, countMove+1]);  
    }

    if (currRow + 1 < size && currCol + 2 < size) {
      queue.push([currRow+1, currCol +2, countMove+1]);  
    }
  } 
  return result;
}

나이트의 이동

📑 문제

문제

입력

출력

✏️ 풀이