문제 개요
체스판과 특수한 나이트 말 K가 하나 있다고 가정해 봅시다. 이 말은 체스판 위에서 L자 모양으로 움직입니다. 말이 (x1, y1) 위치에 있을 때 (x2, y2)로 이동한다면, 그 움직임은 다음과 같이 표현할 수 있습니다.
x2 = x1 ± a ; y2 = y1 ± b 또는 x2 = x1 ± b ; y2 = y1 ± a (단, a와 b는 정수)
우리가 구해야 할 것은 이 체스 말이 (0, 0) 위치에서 출발하여 체스판의 (n-1, n-1) 위치에 도달하기 위해 필요한 최소 이동 횟수입니다. 어떤 위치가 도달할 수 없다면 -1을 표시하고, 도달 가능하다면 실제 이동 횟수를 반환합니다. 결과는 n-1줄로 출력되며, 각 줄 i에는 j마다 필요한 최소 이동 횟수를 나타내는 n-1개의 정수가 포함됩니다.
예를 들어 입력이 n = 6이라면 출력은 다음과 같습니다.
5 4 3 2 5 4 -1 2 -1 -1 3 2 -1 -1 -1 2 -1 -1 -1 -1 5 -1 -1 -1 1
위 그림은 5x5 체스판에서 나이트가 (3, 3) 위치에 있을 때 가능한 이동 경로를 보여줍니다.
출력의 첫 번째 줄에는 말이 (1,1)부터 (1,5)까지 각 위치에 도달하는 데 필요한 최소 이동 횟수가 담깁니다. 이어지는 줄들도 마찬가지로 각각의 i와 j 값에 대한 최소 이동 횟수를 순서대로 나타냅니다.
풀이 접근 방법
이 문제는 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 각 이동 규칙 (i, j)에 대해 시작점 (0, 0)부터 목표점 (n-1, n-1)까지의 최단 거리를 BFS로 계산하고, 이동 규칙의 대칭성을 활용해 중복 계산을 줄이는 것이 핵심입니다.
path_search() 함수 정의
i, j, n 세 값을 인자로 받는 함수를 정의합니다.
temp_list := (-1, -1) 쌍으로 초기화된 새로운 맵
queue_positional := (0, 0) 쌍으로 초기화된 새로운 리스트
ver := [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)] — 8방향 이동 벡터
큐(queue_positional)가 빌 때까지 반복합니다.
current_element := 큐의 첫 번째 원소를 꺼냄
ver의 각 이동 벡터 element에 대해 다음을 수행합니다.
x := element[0] + current_element[0]
y := element[1] + current_element[1]
좌표가 체스판 범위 내(-1 < x < n, -1 < y < n)이고 아직 방문하지 않았다면(temp_list[x, y]가 (-1, -1)인 경우):
temp_list[x, y]에 현재 위치(이전 칸)를 기록하고, (x, y)를 큐 끝에 추가합니다.
만약 x가 n-1이고 y가 n-1이라면 목표 지점에 도달한 것이므로, temp_list를 따라 출발점 (0, 0)까지 역추적하면서 이동 횟수를 세어 반환합니다.
목표 지점에 도달할 수 없다면 -1을 반환합니다.
메인 함수에서의 처리
board := -1로 초기화된 새로운 맵
i를 1부터 n 미만까지, j를 1부터 i 미만까지 반복합니다.
board[i, j]가 아직 계산되지 않았다면(-1인 경우) path_search(i, j, n)를 호출하고, 대칭성을 활용해 board[j, i]에도 같은 값을 저장합니다.
만약 (n - 1)이 i로 나누어떨어진다면 board[i, i] := (n - 1) / i 로 직접 계산합니다.
마지막으로 i를 1부터 n 미만까지 반복하면서 각 행의 board[i, j] 값을 공백으로 구분해 출력하고, 각 행의 마지막 값 board[i, n - 1]을 줄바꿈과 함께 출력합니다.
소스 코드 (Python)
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
from collections import defaultdict
def path_search(i, j, n):
temp_list = defaultdict(lambda: (-1,-1))
queue_positional = [(0, 0)]
ver = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]
while len(queue_positional) > 0:
current_element = queue_positional.pop(0)
for element in ver:
x = element[0] + current_element[0]
y = element[1] + current_element[1]
if -1 < x < n and -1 < y < n and temp_list[x, y] == (-1,-1):
temp_list[x, y] = current_element
queue_positional.append((x, y))
if x == n - 1 and y == n - 1:
count_var = 1
while temp_list[x,y]!=(0,0):
count_var += 1
x, y = temp_list[x,y]
return count_var
return -1
def solve(n):
board = defaultdict(lambda: -1)
for i in range(1, n):
for j in range(1, i):
if board[i, j] == -1:
board[i, j] = path_search(i, j, n)
board[j, i] = board[i, j]
if (n - 1) % i == 0:
board[i, i] = (n - 1) / i
for i in range(1, n):
for j in range(1, n - 1):
print(int(board[i, j]), end = ' ')
print(int(board[i, n - 1]))
solve(6)입력
6
출력
5 4 3 2 5 4 -1 2 -1 -1 3 2 -1 -1 -1 2 -1 -1 -1 -1 5 -1 -1 -1 1