데블스플랜2 기사의 여정, 근데 코딩테스트 곁들인..

넷플릭스에서 데블스플랜2를 보다가 내용에 집중 못하고 잡념만 떠오른 게임이 있다

바로 기사의 여정(여행)

 

기사의 여행 - 위키백과, 우리 모두의 백과사전

 

이거 코테 문제로 있을 것 같은데? DP를.. 아니 백트래킹을..

LeetCode에서 제공하는 문제가 있다! (프로그래머스 점수 올리고 싶다)

다만 경로의 유효성 검증이라서 게임을 진행하는 느낌이 안든다

다른 사이트에서도 유사한 문제를 제공하기는 하나, 실행 검증하는 기능이 없거나, 풀이를 줘버려서 화들짝 꺼버렸다

 

LeetCode

https://leetcode.com/problems/check-knight-tour-configuration/description/

 

Uva Online Judge(10255)

Online Judge

 

GeeksforGeeks

The Knight's tour problem - GeeksforGeeks

 

마음에 드는 문제가 없다

그래서 하나 만들어 본다

풀어도 피스 열개는 없다

 

기사의 현명한 아내: 불가능한 여정 찾기

🔔 문제 설명

기사의 현명한 아내인 당신은 남편이 여정을 빨리 수행해서 복귀하길 바랍니다.

기사가 선택할 수 있는 시작 좌표들 중 "실패하는 위치"를 기사에게 알려주려고 합니다.

n x n 크기의 체스판 위에서 체스의 기사는 L자 형태로 이동할 수 있습니다. (직선으로 2칸, 그 방향에서 좌, 우로 한 칸)
주어진 시작 좌표들에서 각각 기사의 여행이 가능한지를 판단하는 메서드를 구현하세요.

 

👇 이동 규칙 (기사의 이동 방식):

• 두 칸 직진 + 한 칸 옆 (총 8방향)

🧾 입력 파라미터

int n, int[][] positions;

• n (1 ≤ n ≤ 8): 체스판의 한 변 길이 (n x n 보드)
• positions (1 ≤ positions.length ≤ 5): 시작 좌표들의 리스트
  • 각 원소는 int[] 형태로 [x, y]

knightTour(4, [[0, 0], [2, 2]])

 

📤 반환값

• 길이가 positions.length인 boolean[] 배열을 반환
  • 각 원소는 해당 시작 위치에서 모든 칸을 정확히 한 번씩만 방문하는 Knight's Tour가 가능한지를 의미
  • 가능하면 true, 불가능하면 false

✅ 조건 및 제한

• 체스판 내의 모든 칸을 단 한 번씩만 방문해야 합니다.
• 시작 좌표에서 출발하여 모든 칸을 방문하는 경로가 존재하는지 여부만 판단하면 됩니다.
• 경로 출력은 요구되지 않습니다.
• 시간 제한: 모든 시작점마다 최대 2초 이내 (적절한 가지치기 필수)

🧪 예시

// input
int n = 5;
int[][] positions = {
  {0, 0},	// 가능
  {0, 1},	// 불가능
  {3, 4},	// 불가능
  {4, 3}	// 불가능
};

// output
[true, false, false, false]

 

💡 출제자의 힌트(아닐 수도 있음)

• 아예 여정이 불가능한 체스판도 있고, 어디서나 가능한 체스판도 있다
• 막히기 쉬운 길부터 탐색하면 효율적일 수 있습니다
• DP를 쓰면 너무 어려워질 수 있습니다

 

문제 풀이는 다음 기회에...