[코딩테스트] 최소 경로 합 구하기 - 작성중

문제

NxN 격자판이 주어지며, 격자판의 각 칸에는 숫자가 적혀있습니다. 
격자판의 정중앙에서 출발하여, 상하좌우로 이동하며 같은 테두리 안과 그 바깥 테두리 방향으로 이동할 수 있습니다. 
이때, 정중앙으로 돌아올 수 없습니다. 
이동하며 밟은 칸의 숫자를 모두 더해 최소값이 되는 값을 구하세요.

입력:
N (3 ≤ N ≤ 1000, N은 홀수)
board : NxN 크기의 격자판을 1차원 리스트로 표현한 것으로, 길이는 N^2입니다. 각 칸에 있는 숫자는 0 이상 9 이하입니다.

출력:
격자판의 정중앙에서 상하좌우로 이동하며 밟은 칸의 숫자를 모두 더해 최소값이 되는 값을 출력합니다.

입력 예시:
N = 5
board = [9, 3, 9, 9, 9, 5, 2, 7, 8, 9, 8, 1, 5, 8, 9, 6, 1, 8, 7, 9, 9, 9, 8, 9, 9]

출력 예시:
13

설명:
입력 예시 1의 경우, 
정중앙에서 출발하여 왼쪽으로 이동하면 1, 아래로 이동하면 1, 왼쪽으로 이동하면 6을 밟게 되고, 
그 이후 왼쪽으로 이동할 때 격자 바깥으로 나갈 수 있으니까 총 합이 13이 됩니다.

 

내 풀이

1. board를 좌표 (x, y)에 대해 (x, y): 격자 값의 형태로 변환
2. 정중앙 좌표 값 얻기
3. 정중앙 좌표부터 이동할 수 있는 칸 중 제일 적은 값 찾아가며 밟는 값 더하기
4. 제일 마지막 테두리까지 밟은 상태라면 합을 리턴

백트래킹을 사용하면 될 것으로 보임

 

코드

# 1
def get_coord(board, N):
  # 맨 왼쪽 위는 (0, 0)
  # 맨 윗줄은 (0, 0), (0, 1), (0, 2), (0, 3), (0, 4)
  # 즉, index를 N으로 나눴을 때의 나머지 -> 0, 1, 2, 3, 4 를 5로 나누고 나머지 -> (x, y)에서의 y가 됨
  # index를 N으로 나눴을 때의 몫 -> (x, y)에서의 x
  coord = {}
  for i, value in enumerate(board):
    x = i // N
    y = i % N
    coord[(x, y)] = value
  return coord

# 2
def get_center(N):
  return (N // 2, N // 2)

백트래킹에 대해 이론 정도만 알고 제대로 공부하기 전에 문제를 접했기 때문에
여기까지밖에 구현할 수 없었다.

 

이후 공부한 내용을 토대로 문제를 푼다면 다음과 같다.

ㅇㅇ