Python 3

나선형 배열은 다음과 같은 범주를 갖는다:

• 0th: 1
• 1th: 2 .. 9
• 2th: 10 .. 25
• 3th: 26 .. 49
• ...
• 즉, nth 범주의 최대값은 (2 * (n + 1) - 1) ** 2 (단, n >= 0) ... Eq.(1)

자연수 num이 주어질 때, Eq.(1)을 통해 num이 포함되는 범주 n을 구할 수 있다.

또한, nth 범주에 대해 각 변의 중앙값은 (e.g. 2th 범주에서는 11, 15, 19, 23)

1. s1 = 4 * n ** 2 - 3 * n + 1
2. s2 = s1 + 2 * n
3. s3 = s2 + 2 * n
4. s4 = s3 + 2 * n

이며,

num이 속하는 범주 nth에 대해 계산되는 s1, s2, s3, s4로 부터의 |num- s|의 최소값을 d라고 할 때,

최소 이동거리는 n + d이다.

def main():
    num = int(input())
    rst = get_min_distance(num)
    print(rst)


def get_nth(num: int):
    """num이 속하는 범주(nth) 계산"""
    nth = 0
    last_val = 1
    while num > last_val:
        nth += 1
        last_val = (2 * (nth + 1) - 1) ** 2

    return nth


def get_min_distance(num: int):
    """num으로 이동하는 최소 거리 계산"""
    nth = get_nth(num)
    if num == 1:
        return nth

    points = [4 * nth ** 2 - 3 * nth + 1]
    for i in range(3):
        points.append(points[-1] + nth * 2)
    min_distance = nth + min(abs(num - point) for point in points)

    return min_distance


if __name__ == '__main__':
    main()

나선형 맵에서 1이 원짐일 때 특정 숫자의 좌표를 구하는 문제. n보다 작으면서 가장 큰 홀수 제곱근 m을 찾은 뒤, m^2과의 차이를 알면 좌표가 바로 나옵니다.

시간복잡도는 제곱근 m을 찾는데 필요한 O(log n). 공간복잡도는 O(1)

#include<stdio.h>
#include<algorithm>
using namespace std;
long long int n, m;
long long int minsqrt(long long int x) {
    long long int l = 1;
    long long int r = x+1;
    long long int mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (mid <= x / mid) {
            if (mid * mid == x)return mid;
            else if (mid * mid < x)l = mid + 1;
            else r = mid;
        }
        else {
            r = mid;
        }
    }
    return l - 1;
}
int main() {
    int i, j, k, l;
    while (~scanf("%lld",&n)) {
        if (n == 1) {
            printf("0\n"); continue;
        }
        m = minsqrt(n-1);
        if (!(m & 1))m--;
        long long int mz = (m+1) / 2;
        long long int diff = n - m * m ;
        int type = 0;
        while (diff > mz*2) {
            diff -= mz*2;
            type++;
        }
        long long int x, y;
        if (type == 0)
        {
            x = mz;
            y = -mz + diff;
        }
        else if (type == 1) {
            x = mz - diff;
            y = mz;
        }
        else if (type == 2) {
            x = -mz;
            y = mz - diff;
        }
        else {
            x = -mz + diff;
            y = -mz;
        }
        printf("%lld\n", abs(x) + abs(y));
    }
}

input

1
3
17
19
26
2550
2573
1000000000
1000000000000000000
987654321987654321
2147483647
1048576

output

0
2
4
2
5
49
28
17493
999999999
987801760
41706
1023

스캐너를 이용해봤습니다. 출제자의 의도와 많이 다를 수도 있습니다.

package practice;

import java.util.Scanner;

public class What_Should_I_make {
    public static void main(String[] args) {

        //      1부터 차례대로 다음과 같이 정렬했을 때, 
        //      숫자 N(1 <= N <= 10^9)을 입력받아서 
        //      1부터 N까지 가는 최단거리를 계산하는 프로그램을 작성하세요. 
        //      (상, 하, 좌, 우로만 움직일 수 있고 대각선으로는 움직일 수 없다.)

        Scanner sc = new Scanner(System.in);

        int[][] arr;
        int size = 0;//크기
        int num = 1;//시작수
        int x = 0;//x축
        int y = 0;//y축
        System.out.print("홀수만 입력: ");
        size = sc.nextInt();
        arr = new int[size][size];//사용자가 지정한 사이즈

        x = size/2;
        y = size/2;
        //정중앙에서 시작



        int a = 1;//순서변수
        int sum = 1;//한줄로 숫자를 생성하기위한 변수

        arr[y][x] = num;
        //변의길이에 따른 나선배열 생성
        outer : while(num <= size*size) {


            for(int i = 0; i < sum; i++) {
                if(a == 1){ x += 1; num++; 
                if(num == size*size+1) {
                    break outer;
                }//규격외로 넘어가는 숫자생성 방지 
                arr[y][x] = num; }//오른쪽으로 생성
                if(a == 2){ y -= 1; num++; arr[y][x] = num; }//위로 생성
            }//for

            for(int i = 0; i < sum; i++) {
                if(a == 3){ x -= 1; num++; arr[y][x] = num; }//왼쪽으로생성
                if(a == 4){ y += 1; num++; arr[y][x] = num; }//아래로 생성
            }//for


            if( a == 4 ) {
                a = 1;
                sum++;
            }else if( a == 2){
                sum++;
                a++;
            }else if( a==3 || a==1 ){
                a++;
            }//진행순서 설정


        }//while

        //배열 출력 코드
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j]+"    ");
            }//inner
            System.out.println();
        }//output


        System.out.println("-------------------------------");



        int number = 0;
        System.out.println("5번 측정하세요");
        while(number != 5) {

            System.out.print("1에서 거리를 측정할 숫자 값: ");

            int n = sc.nextInt();
            int xLength;
            int yLength;

            for (int i = 0; i < arr.length; i++) {

                for (int j = 0; j < arr[i].length; j++) {   
                    if(n == arr[i][j]) {

                        if( i >= (size/2) ) {

                            yLength = i-(size/2);
                        }else{
                            yLength = (size/2)-i;
                        }//y값 거리측정

                        if( j >= (size/2) ) {
                            xLength = j-(size/2);
                        }else {
                            xLength = (size/2)-j;
                        }//x값 거리측정
                        System.out.println( xLength + yLength );
                    }//if

                }//inner

            }//outer
            number++;
        }//while



    }//main
}

출력결과

홀수만 입력: 7

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

5번 측정하세요

1에서 거리를 측정할 숫자 값: 25

4

1에서 거리를 측정할 숫자 값: 47

4

1에서 거리를 측정할 숫자 값: 49

6

1에서 거리를 측정할 숫자 값: 37

6

1에서 거리를 측정할 숫자 값: 44

5

Ruby

4변 중 가까운 변의 가운데 지점으로 거리 계산

distance = lambda do |given_num|
  side_length = (given_num ** 0.5).ceil.then { |s| s + ((s % 2) ^ 1) }
  radius, last_num = side_length / 2, side_length ** 2
  nearests = 4.times.map { |nth| last_num - ((nth * 2 + 1) * radius)}
  nearests.map { |vert| radius + (vert - given_num).abs }.min
end
distance_from_spiral_center = -> { puts gets("\n\n").split.map(&:to_i).map(&distance) }  

Test

test_numbers = [1, 3, 17, 19, 26, 2550, 2573]
expect(test_numbers.map(&distance)).to eq [0, 2, 4, 2, 5, 49, 28]
expect(distance[10**9]).to eq 17493
expect(distance[10**99]).to eq 40977302808488135725000812741163967580261426850331327105897628076954533744596746239

# for perfomance test
require 'benchmark'

expect( Benchmark.realtime { distance[10**9] } ).to be < 0.0001
expect( Benchmark.realtime { distance[10**100] } ).to be < 0.0001

Output

distance_from_spiral_center.call
1
3
17
19
26
2550
2573

0
2
4
2
5
49
28

import math

inp = int(input("INPUT : "))

x, y, result, nmax, dx, dy = 0, 0, 0, 0, 0, 1

DXDY_LIST,ADDRESS_IN_LIST  = [(0, 1), (-1, 0), (0, -1), (1, 0)], 0

## nmax 계산
while True :
    if math.sqrt(inp)%2 == 1 :
        result=(math.sqrt(inp)-1)
        break
    elif (2*nmax+1)*(2*nmax+1) > inp :
        break
    else :
        nmax += 1
x, y, result = nmax, -nmax+1, (2*(nmax-1)+1)*(2*(nmax-1)+1)+1

# 좌표 계산
while True :
    if nmax == 0 :
        print((math.sqrt(inp)-1))
        break
    if result == inp :
        print(abs(x)+abs(y))
        break
    else :
        x, y = x+dx, y+dy
        result += 1
        if abs(x) > nmax or abs(y) > nmax :
            x, y = x-dx, y-dy
            ADDRESS_IN_LIST = (ADDRESS_IN_LIST+1)
            dx = DXDY_LIST[ADDRESS_IN_LIST][0]
            dy = DXDY_LIST[ADDRESS_IN_LIST][1]
            x, y = x+dx, y+dy

먼저 입력된 수가 몇 번째 껍질에 들어있는지 계산하고, 그 다음부터는 수를 하나하나 늘려가며 좌표를 구하는 식으로 계산하였습니다.

결과

INPUT : 1000000000
17493

INPUT : 2550
49

INPUT : 26
5

입력된 수가 (2n+1)^2일 때의 처리가 매끄럽지 못 하는 등 미숙한 점이 많네요 ㅠㅠ

코딩 초보가 무식하게(방법적으로...) Python으로 짜봤습니다.

해당 숫자(number)를 포함하는 최소 크기의 정사각형 형태의 나선 배열을 가정해두고(한변의 길이가 size),

맨 왼쪽 하단 숫자 좌표를 (0,0)으로 두었을때

1의 위치 좌표 계산

나선의 최대 숫자에서 number까지의 거리 계산하여 맨 바깥쪽 껍질에서의 위치 좌표 계산

1과 number의 x좌표끼리의 차이와 y좌표끼리의 차이를 더하여 거리를 계산했습니다.

number의 좌표 구하는 부분이 영 마음에 안드네요.

import math

# 숫자 입력
number = int(input("Input Number : "))

# 해당 number를 포함하는 정사각 나선의 한변의 길이
size = math.ceil(math.sqrt(number))

# 정사각형 나선 최대 숫자에서 number까지의 거리
dist = size**2 - number

# number가 최대 숫자와 같은 변에 있는지 확인 및 좌표 계산을 위한 변수, edge > 0인 경우 변이 바뀜
edge = dist - (size - 1)

if size%2 == 0:
    # 나선의 한변의 길이가 짝수인 경우
    # (0,0) 기준 1의 위치 좌표
    [x1, y1] = [int(size/2 - 1), int(size/2)]

    # (0,0) 기준 number의 위치 좌표
    # 최대 숫자와 number가 같은 변에 있는지 확인
    if edge > 0:
        [x2, y2] = [size - 1, edge]
    else:
        [x2, y2] = [dist, 0]

else:
    # 나선의 한변의 길이가 홀수인 경우
    # (0,0) 기준 1의 위치 좌표
    [x1, y1] = [int(size/2), int(size/2)]

    # (0,0) 기준 number의 위치 좌표
    # 최대 숫자와 number가 같은 변에 있는지 확인
    if edge > 0:
        [x2, y2] = [0, edge]
    else:
        [x2, y2] = [-edge, size - 1]

# 1에서 부터 number의 거리
dist_from_one = abs(x1 - x2) + abs(y1 - y2)

print(dist_from_one)

Javascript(ES6)...

• 반복문으로 위치 추적

`1 부터 입력한 숫자 n 까지 반목문 생성, 반복문 안에서 처음 1 과의 상대적 위치를 나타내는 x, y 변수 계속 조정, 다음 칸이 경계를 벗어나면 방향 전환, Math.abs(x) + Math.abs(y) 가 1 에서 n 까지의 최단거리가 됨`;

function spiral_a(n) {

    let _n = Math.max(1, Math.min(1000000000, n));

    // x, y 는 1 과의 상대적 위치, dx, dy 는 x, y 가 진행할 방향, border 는 경계의 크기
    let [x, y, dx, dy, border] = [-1, 0, 1, 0, 0];

    // 반복문을 돌며 x, y 계속 추적
    for(let i = 1; i < _n + 1; i++) {
        [x, y] = [x + dx, y + dy];

        // x, y 의 위치가 오른쪽 아래 border 에 모두 닿으면 경계 확장
        if(x == border && y == border) { border++; }

        // x, y 의 다음 진행방향이 border 를 벗어나면 방향전환
        if(x + dx < -border || border < x + dx || y + dy < -border || border < y + dy) {
            [dx, dy] = [dy, -dx];
        }
    }

    console.log(`${Math.abs(x) + Math.abs(y)}`);
}

spiral_a(1);                // 0
spiral_a(3);                // 2
spiral_a(17);               // 4
spiral_a(19);               // 2
spiral_a(26);               // 5
spiral_a(2550);             // 49     
spiral_a(2573);             // 28
// spiral_a(1000000000);    // 17493    시간이 너무 오래 걸림

• 규칙성을 찾아내어 계산

`Spiral 구조를 보면 오른쪽 아래 대각선 방향으로 숫자의 규칙성이 보임, 1, 9, 25, 49, 81, ... 이며 구체적으로는 아래와 같음

border                     0    1    2    3    4    5    6 ...
대각선 숫자 corner_n        1    9   25   49   81  121  169 ...
중심에서 거리 distance      0    2    4    6    8   10   12 ...

corner_n = (border * 2 + 1)**2, distance = border * 2 로 나타낼 수 있음

반복문을 돌며 주어진 숫자 n 을 바로 초과하는 corner_n 과 distance 를 구한 뒤, n 과 corner_n 차이에 대한 세부적인 조정으로 distance 재계산`;

function spiral_b(n) {

    let _n = Math.max(1, Math.min(1000000000, n));

    // 반복문으로 corner_n, distance 계산
    let [border, corner_n, distance] = [-1, 0, 0];
    do {
        border++;
        corner_n = (border * 2 + 1)**2;
    } while(corner_n < _n);
    distance = border * 2;

    // n 과 corner_n 차이 조정
    let sub = corner_n - _n;
    if(sub != 0) {
        sub %= (border * 2);
        if(sub > border) { sub = border * 2 - sub; }
        distance -= sub;
    }

    console.log(distance);
}

spiral_b(1);                // 0
spiral_b(3);                // 2
spiral_b(17);               // 4
spiral_b(19);               // 2
spiral_b(26);               // 5
spiral_b(2550);             // 49     
spiral_b(2573);             // 28
spiral_b(1000000000);       // 17493

C언어로 해봤습니다. 초보라서..그냥 수열의 특징을 이용해 봤습니다.

1이 입력되었을 경우에는 그냥 0을 출력하도록 하고 2이상일 경우 1에서 부터 맨 마지막의 네 코너의 수를 구해서 코너까지 도달하는 거리 - 그 숫자에서 코너까지의 거리 를 계산했습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int getShortcut(int number);

int main() 
{
    int input, result;
    scanf("%d", &input);

    if (input < 2)      //1의 경우 계산을 하지 않고 0출력
    {
        printf("0");
    }
    else
    {
        printf("%d", getShortcut(input));
    }

    return 0;
}

int getShortcut(int number)
{
    int Nbox = 1;           //몇번째 나선인지 저장할 변수
    int EndOfLastBox = 0;   //비교에 사용할 이전 박스의 마지막 수
    int EndOfCuurentBox = 0;    //비교에 사용할 현재 박스의 마지막 수
    int footOnBorderCorner[5] = { 0, }; //이적박스의 마지막 수부터, 현재박스의 각 코너의 수를 저장할 배열
    int minusStep = 0;  //현재 수에서부터 각 코너까지의 거리를 저장할 변수
    int temp1 = 0, temp2 = 0;   //minusStep에 저장하기전 비교에 사용할 임시변수

    //몇번째 나선에 있는지 확인
    do
    {
        EndOfLastBox = (2 * (Nbox - 1) - 1)* (2 * (Nbox - 1) - 1);
        EndOfCuurentBox = (2 * Nbox - 1)* (2 * Nbox - 1);
        if (number > EndOfLastBox && number <= EndOfCuurentBox)
            break;
        Nbox++;
    } while (1);


    //각 나선에서 어느 변에 있는지 확인하여 코너로부터의 거리값을 구함.
    for (int i = 0; i < 5; i++)
    {
        footOnBorderCorner[i] = EndOfLastBox + ((Nbox-1)*2 * (i));

        if (i > 0)
        {
            if (number == footOnBorderCorner[i])   //만약 코너값 중에 일치하는 것이 있으면 minusStepㅇ  =0 
            {
                minusStep = 0;
            }
            else if (number > footOnBorderCorner[i - 1] && number < footOnBorderCorner[i])  //각 변에 속하면
            {
                temp1 = footOnBorderCorner[i] - number; // 큰수로부터의 거리
                temp2 = number - footOnBorderCorner[i - 1]; //작은수까지의 거리

                if (temp1 > temp2)  //작은쪽을 minusStep에 할당
                {
                    minusStep = temp2;
                }
                else
                {
                    minusStep = temp1;
                }

                break;
            }
        }
    }


    return ((Nbox-1)*2) - minusStep;    
}

풀이에 있는 mohenjo이라는 아이디를 가진 분의 개념을 바탕으로 java언어를 가지고 만들었습니다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Main main = new Main();

        int num;
        Scanner scan = new Scanner(System.in);
        num= scan.nextInt();//숫자입력

        int check = main.get_min_distance(num);
        System.out.println("입력한 숫자값: " + num);
        System.out.println("문제의 답: " + check);

    }

    public int get_nth(int num) {//num이 속하는 범주 계산.
        int nth=0;
        int last_val=1;

        while(num>last_val) {
            nth=nth+1;
            last_val =(int) Math.pow((2 * (nth+1) -1 ), 2);
        }
        return nth;
    }


    public int get_min_distance(int num){//num으로 이동하는 최소거리 계산
        int nth= get_nth(num);
        if(num==1) {
            return nth;
        }

        int points = 4*(int)Math.pow(nth, 2) - 3*nth + 1;
        int[] arr = new int[4];
        for(int i=0;i<4;i++) {
            arr[i]=points+i*2*nth;
        }

        int[] min_distance = new int[4];
        for(int i=0;i<4;i++) {
            min_distance[i]= nth + Math.abs(num-arr[i]);
        }

        //최소값구하기
        int min = min_distance[0];
        for(int i=0; i<min_distance.length;i++) {
            if(min>min_distance[i]) {
                min=min_distance[i];
            }
        }

        return min;
    }

}

올리는 건 처음이라 이게 맞는지 모르겠는데 확인해주세요.

n = 0 
x = (random_number) #input 할 수

while True:
    if (2*n - 1)**2 < x <= (2*n + 1)**2:
        break
    else:
        n += 1


# n => n 번째 껍질에 존재한다는것을 알려준다.
# 껍질 => 2~9까지는 1번껍질, 10~25번까지는 2번껍질....
# 배열해보시면 n번껍질이 무엇인지 알수있을것입니다.

list1 = [i for i in range(2*n, n, -1)]
list2 = [j for j in range(n, 2*n)]
list3 = list1 + list2
list4 = list3*4

#젤 큰수로부터 몇번째 있는가에 따라 나눠지는 도달횟수, n껍질 기준
#ex) 25로부터 시작되는 2번껍질을 에 도달하는 최소횟수를 리스트(list4)로 풀면 [4,3,2,3,4,3,2,4,3,4,3,2,3,4,3,2,3] 이됩니다.
#4짝으로 반복이 되는데 사각형의 4개의 면을 의미합니다.

k = (2*n + 1)**2 - x # 위에 정한 리스트에 몇번째에 위치하는가를 나타내기위해 k를 썼습니다.

final_result = list4[k] #최종결과는 리스트를 인덱스한것으로 나타냈습니다.

print(final_result)

#함수로 나타내지 못한점 죄송합니다. 초보라서... 수정해주시면 감사하겠습니다.

처음으로 문제 풀고 올려봅니다. 확인해주시면 감사하겠습니다!

def spiral(N):

    i = 1


    while True:

        if N <= (2*i -1) ** 2:
            break

        i += 1


    if i == 1: return 0

    temp = 2*i -1

    t_list = []

    for j in range(temp**2 - temp + 2,temp**2+1):
        t_list.append(j)

    while True:

        if N in t_list : break

        else:
            for k in range(len(t_list)):
                t_list[k] -= temp -1

    result = (i-1) + abs(t_list.index(N) - (i-2))

    return result

파이썬 3입니다

정사각형 모양의 껍질을 먼저 찾았습니다 (n 번째 껍질)

import math

N = int(input())

n = math.ceil((math.sqrt(N) + 1) / 2)

print('1부터 {}까지의 거리는 {}이다'.format(N, n - 1 + abs((N - (2 * n - 3) ** 2) % (2 * n - 2) - n + 1)))

N=int(input("""1부터 N까지 가는 최단거리를 출력합니다.
N(1<=N<=10^9)을 입력하십시오:"""))
ON=N
N=int(N**(1/2))**2
border=int(N**(1/2))+1
onetoS=int(N**(1/2))-1
lst=[onetoS,onetoS+1]
n,a=onetoS+1,1
while len(lst)<2*border:
    if border%2==0:
        n=n-a
        lst.append(n)
        if n==int(border/2):
            a=-a
        elif n==border:
            a=-a
    else:
        n=n-a
        lst.append(n)
        if n==int(border/2):
            a=-a
        elif n==(border-1):
            a=-a
d=dict()
for k in range(N,N+len(lst)):
    d[k]=lst[k%N]
if ON<=3:
    d={1:0,2:1,3:2}
print(d[ON])

결과

1부터 N까지 가는 최단거리를 출력합니다.
N(1<=N<=10^9)을 입력하십시오:1000000000
17493

import math

n=int(input())
def check_far(n):
    c=math.sqrt(n)
    n_2=math.ceil(c)
    if n_2%2==1:
        return (n_2-1)/2
    else: return n_2/2

def check(n,garo):
    start=(garo*2+1)**2
    gap=start-n
    if gap>=0 and gap<=garo*2:
        mid= garo
        return garo+abs(gap-mid)
    elif gap>garo*2 and gap<garo*4:
        mid= 3*garo
        return garo+ abs(gap-mid)
    elif gap>=garo*4 and gap<=garo*6:
        mid= 5*garo
        return garo+abs(gap-mid)

    else:
        mid=7*garo
        return garo + abs(gap-mid)



garo=check_far(n)
print(int(check(n,garo)))

package helical_ordering;
import java.util.Scanner;
public class HelicalOrdering {

    public static void main(String[] args) {
        //1 <= N <= 9801
        Scanner in = new Scanner(System.in);
        int n=100, N=n*n;
        int i=50, j=50, k=1, p, q, input;
        int[][] board = new int[n][n];
        int direction=0; // 0 오른쪽, 1 위쪽, 2 왼쪽, 3 아래쪽

        do {
            System.out.print("Input:");
            input = in.nextInt();
            if(input==0) break;

            /*나선형 배열 만들기*/
            board[50][50]=1; //첫 스텝
            while(k<input){
                if(direction==0) { //오른쪽
                    board[i][++j]=++k;
                    if(board[i-1][j]==0)
                        direction=1;
                }
                else if(direction==1) { //위쪽
                    board[--i][j]=++k;
                    if(board[i][j-1]==0)
                        direction=2;
                }
                else if(direction==2) { //왼쪽
                    board[i][--j]=++k;
                    if(board[i+1][j]==0)
                        direction=3;
                }
                else if(direction==3) { //아래쪽
                    board[++i][j]=++k;
                    if(board[i][j+1]==0)
                        direction=0;
                }
                else System.out.println("It should not reach here.");
            }   

            int result=0;
            result+=(i>50)?i-50:50-i;
            result+=(j>50)?j-50:50-j;

            System.out.println("Output:"+result);       
        }while(input!=0);

        /*print*//*
        for(p=0; p<n; p++) {
            for(q=0; q<n; q++) {
                if(board[p][q]<1000)
                    System.out.print(" ");
                if (board[p][q]<100)
                    System.out.print(" ");
                if (board[p][q]<10)
                    System.out.print(" ");
                System.out.print(" "+board[p][q]);
            }
            System.out.println();
        }*/
    }
}

Input:1
Output:0
Input:3
Output:2
Input:17
Output:4
Input:19
Output:2
Input:26
Output:5
Input:2550
Output:49
Input:2573
Output:28
Input:0

from math import sqrt, floor


# 1의 위치가 원점 (0, 0)일 때 n의 좌표를 구한다.
def find_pos(n):
    m = (floor(sqrt(n-1)) + 1) // 2 # 몇 번째 나선인가? => 0, 1, 2, 3, ...
    l = m * 2                       # (한 변의 길이 - 1) => 0, 2, 4, 6, ...

    # 하변
    k = (l + 1) ** 2    # k는 각 변에서 가장 큰 수 => 1*1, 3*3, 5*5, 7*7, ... 에서 시작
    if k - l < n <= k:
        return m, m - (k - n)

    # 좌변
    k -= l
    if k - l < n <= k:
        return m - (k - n), -m

    # 상변
    k -= l
    if k - l < n <= k:
        return -m, -m + (k - n)

    # 우변
    k -= l
    return -m + (k - n), m


n = int(input())
x, y = find_pos(n)
print(abs(x) + abs(y))

자바로 풀어봤습니다.

import java.util.Scanner;

public class test {
    public static void paintingArray(int[][] result, int m, int n) {
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                System.out.printf("%3d", result[i][j]);
            }
            System.out.println();
        }
    }

    public static int[] findPosition(int[][] result, int Number) {
        int[] position = new int[2];

        for(int i=0; i<result.length; i++) {
            for(int j=0; j<result[0].length; j++) {
                if(result[i][j]==Number) {
                    position[0] = j;
                    position[1] = i;
                }
            }
        }

        return position;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        // 배열 사이즈 입력
        System.out.print("배열의 사이즈를 입력(m:row, n:column):");
        int m = scan.nextInt();
        int n = scan.nextInt();

        // 배열 초기화
        int result[][] = new int[m][n];

        // 배열 원소 압력
        int element = m*n, direction=0, row=0, column=0;

        while(element>0) {
            switch(direction) {
            case 0:
                for(int j=column; j<n-1-column; j++) {
                    result[row][j] = element;
                    element--;
                }
                direction++;
                break;
            case 1:
                for(int i=row; i<m-1-row; i++) {
                    result[i][n-1-column] = element;
                    element--;
                }
                direction++;
                break;
            case 2:
                for(int j=n-1-column; j>column; j--) {
                    result[m-1-row][j] = element;
                    element--;
                }
                direction++;
                break;
            case 3:
                for(int i=m-1-row; i>row; i--) {
                    result[i][column] = element;
                    element--;
                }
                direction=0;
                column++;
                row++;
                break;
            }
        }

        // 결과 출력
        paintingArray(result, m, n);    

        // position of zero
        int[] zeroPosition = findPosition(result, 1);

        // 자연수 N 입력
        System.out.print("\n최단거리를 계산하고 싶은 N을 입력:");
        int N = scan.nextInt();

        // position of N
        int[] NPosition = findPosition(result, N);

        //distance 계산
        int distance = 0;
        for(int i=0; i<2; i++) {
            distance += Math.abs(zeroPosition[i] - NPosition[i]);
        }
        System.out.printf("1부터 %d까지 가는 최단거리 : %d", N, distance);
    }
}

# 1    3    13    31 -  -  -  - 4n^2 - 2n + 1
#   2    10    19    -  -  -  - 2 + 8(n-1)
#     8     8


def shortestDistance(N):
    if N < 4:
        return N - 1

    i = 0
    S = 1
    while N >= S:
        i += 1
        S = 4 * i ** 2 - 2 * i + 1

    i -= 1
    S = 4 * i ** 2 - 2 * i + 1
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    x, y = i, i

    m = N - S
    cm = 2 * i
    idx = 0
    for j in range(1, m + 1):
        x += dx[idx]
        y += dy[idx]
        if idx < 2 and j % cm == 0:
            idx += 1
        elif j == 3 * cm + 1:
            idx += 1
        #print(x, ' ', y)

    return abs(x) + abs(y)


N = int(input('숫자 N을 입력하세요: '))
print(shortestDistance(N))