문제 태그

• 구성적 알고리즘
• 격자 그래프
• 해밀턴 경로
• 홀짝성

한국어 문제 해석

N 곱하기 N 격자에서 말은 처음에 (1, 1)에 있다. 정확히 $N^2 - 2$번 이동해서 (N, N)에 도착해야 한다.

이동은 상하좌우 인접한 칸으로만 가능하다. 전체 칸 중 (A, B)만 방문하지 않고, 나머지 모든 칸은 정확히 한 번씩 방문해야 한다. 중간에 (1, 1)이나 (N, N)을 다시 방문하는 것도 불가능하다.

가능하면 이동 문자열을 하나 출력하고, 불가능하면 No를 출력한다.

문제 요약

• (A, B)를 제외한 모든 칸을 한 번씩 방문하는 경로를 구성한다.
• 시작은 (1, 1), 끝은 (N, N)이다.
• 답이 여러 개면 아무거나 출력해도 된다.

예시 워크스루

N이 4이고 제외 칸이 (3, 2)라고 하자.

현재 코드는 먼저 위쪽 2행 묶음을 가로로 훑는다.

• 1행을 오른쪽 끝까지 간다.
• 아래로 내려간 뒤 2행을 왼쪽 끝까지 돌아온다.