문제
6 x 6 체스판에서 36개 좌표가 순서대로 주어질 때, 유효한 나이트 투어인지 검증하라.
입력
36줄에 걸쳐 나이트가 방문하는 좌표가 주어진다 (예: A1, F6).
출력
유효하면 "Valid", 아니면 "Invalid"를 출력한다.
예제
| 입력 | 출력 |
|---|---|
A1 C2 ... (36줄) | Valid 또는 Invalid |
풀이
36개 좌표를 순서대로 검증하여 나이트 투어 조건을 확인한다.
- 각 좌표를 (행, 열)로 변환한다
- 연속 좌표 간 이동이 나이트 규칙(행차 1, 열차 2 또는 행차 2, 열차 1)을 만족하는지 확인한다
- 모든 36칸이 정확히 한 번씩 방문되었는지 확인한다
- 마지막 칸에서 첫 칸으로의 이동도 나이트 규칙을 만족하는지 확인한다
핵심 아이디어: 중복 방문 검사(Set)와 인접 이동 검사를 동시에 수행하며, 마지막→첫 칸 이동까지 확인해야 순환 투어가 된다.
코드
const solution = (input) => {
const coords = [];
for (let i = 0; i < 36; i++) {
const s = input[i].trim();
const col = s.charCodeAt(0) - 65;
const row = +s[1] - 1;
coords.push([row, col]);
}
const visited = new Set();
const isKnight = (a, b) => {
const dr = Math.abs(a[0] - b[0]);
const dc = Math.abs(a[1] - b[1]);
return (dr === 1 && dc === 2) || (dr === 2 && dc === 1);
};
for (let i = 0; i < 36; i++) {
const key = `${coords[i][0]},${coords[i][1]}`;
if (visited.has(key)) return "Invalid";
visited.add(key);
if (i > 0 && !isKnight(coords[i - 1], coords[i])) return "Invalid";
}
if (!isKnight(coords[35], coords[0])) return "Invalid";
if (visited.size !== 36) return "Invalid";
return "Valid";
};
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));복잡도
- 시간: O(1) (고정 36칸)
- 공간: O(1)