[BOJ] 18404 - 현명한 나이트 (Python, JavaScript)

 

 

아이디어

 

BFS로 나이트가 체스판의 각 칸에 방문하기 위한 최소 이동 횟수를 구한다.

 

 

풀이 #1 (Python)

 

나이트가 이동할 수 있는 위치의 변화 값을 튜플로 리스트 delta에 저장한다.

 

체스판 내 각 칸의 최소 이동 횟수를 저장하기 위해 (N+1)×(N+1) 크기의 0으로 채워진 2차원 리스트 visited를 생성한다.

visited에서 나이트의 초기 위치를 1로 저장하고, 큐 queue에 나이트의 초기 위치를 저장한다.

 

while문에서 BFS로 나이트가 이동할 수 있는 칸으로 이동하며 visted에 최소 이동 횟수를 저장해 나간다.

체스판의 모든 칸에 대해 최소 이동 횟수를 저장한 후, for문에서 상대편 말을 잡기 위한 최소 이동 횟수들을 출력한다.

 

import sys

input = sys.stdin.readline

delta = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]

def solution():
    N, M = map(int, input().split())
    X, Y = map(int, input().split())
    visited = [[0]*(N+1) for _ in range(N+1)]
    visited[X][Y] = 1
    queue = [(X, Y)]
    res = []
    while queue:
        i, j = queue.pop(0)
        for di, dj in delta:
            if N >= i+di > 0 and N >= j+dj > 0:
                if visited[i+di][j+dj] == 0:
                    queue.append((i+di, j+dj))
                    visited[i+di][j+dj] = visited[i][j]+1
    for _ in range(M):
        A, B = map(int, input().split())
        res.append(visited[A][B]-1)
    print(*res)

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작하며, 큐 queue의 첫 번째 값을 꺼내기 위해 shift 메서드를 사용한다.

 

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

const delta = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]];

const [N, M] = input[0].split(' ').map(Number);
const [X, Y] = input[1].split(' ').map(Number);
let visited = Array.from(Array(N+1), () => Array(N+1).fill(0));
visited[X][Y] = 1;
let queue = [[X, Y]];
let res = [];
while (queue.length) {
    const [i, j] = queue.shift();
    for (const [di, dj] of delta) {
        if (N >= i+di && i+di > 0 && N >= j+dj && j+dj > 0) {
            if (visited[i+di][j+dj] == 0) {
                queue.push([i+di, j+dj]);
                visited[i+di][j+dj] = visited[i][j]+1;
            }
        }
    }
}
for (let i=2; i<M+2; i++) {
    const [A, B] = input[i].split(' ').map(Number);
    res.push(visited[A][B]-1);
}
console.log(res.join(' '));