백준[1913] 달팽이

백준[1913] 달팽이

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	3198	1695	1397	55.657%

 

문제

홀수인 자연수 N(3≤N≤999)이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N*N의 표에 늘어놓을 수 있다.

9	2	3
8	1	4
7	6	5

25	10	11	12	13
24	9	2	3	14
23	8	1	4	15
22	7	6	5	16
21	20	19	18	17

N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

 

입력

첫째 줄에 홀수인 자연수 N이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

 

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

 

예제 입력 1

7
35

 

예제 출력 1

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

 

풀이

• 방향 결정해주는 변수 (direc)
• 몇 칸 갈지 설정해주는 변수 (count)
• 넣을 값 (count)
• 처음 값 (xtemp, ytemp)
• 방향은 위 오른 아래 왼쪽으로 결정되어 있다.
• 이 방향에 따라 가야하는 칸수가 달라진다.
• 넣어야 하는 값도 계속해서 변한다.

 

n = int(input())
find = int(input())

snail = [[0] * n for i in range(n)]
value = 1
direc = 1
count = 1
xtemp = int((n - 1) // 2)
ytemp = int((n - 1) // 2)
snail[xtemp][ytemp] = value

while value != n * n:
    if (direc == 1):
        for i in range(count):
            value += 1
            xtemp -= 1
            snail[xtemp][ytemp] = value
            if (value == n*n):
                break

        direc = 2

    elif (direc == 2):
        for i in range(count):
            value += 1
            ytemp += 1
            snail[xtemp][ytemp] = value
        count += 1
        direc = 3

    elif (direc == 3):
        for i in range(count):
            value += 1
            xtemp += 1
            snail[xtemp][ytemp] = value

        direc = 4

    elif (direc == 4):
        for i in range(count):
            value += 1
            ytemp -= 1
            snail[xtemp][ytemp] = value
        count += 1
        direc = 1

for i in range(n):
    for j in range(n):
        print(snail[i][j], end=" ")
        if (snail[i][j] == find):
            save_x = i+1
            save_y = j+1
    print()

print(save_x, save_y)

 

선생님 풀이

• 가면서 못가는 곳이 있을때 방향을 바꾼다.
• 제약 조건을 설계하는데 있어 반대방향으로 가는게 좋다. while(now_num > 0)
• 벽은 x < 0, x >= n, y < 0, y >= n, 그리고 방안에 들어가 있는 값이 0이 아닐 경우 벽으로 간주한다.
• 벽에 부딪혔을 때, 방향을 바꾸는데, 이 순서를 0, 1, 2, 3으로 설정해두고 바꾼다.
• 거꾸로 시작했으므로 아래, 오른쪽, 위, 왼쪽 이 반복될 것

 

import  copy

n = int(input())
m = int(input())
snail = []
temp = []

for i in range(n):
    temp.append(0)

for i in range(n):
    snail.append(copy.deepcopy(temp))

move = [[0,1],[1,0],[0,-1],[-1,0]]
d = 0
now_x = 0 ; now_y = 0 ; now_num = n*n

while(now_num > 0):
    snail[now_y][now_x] = now_num
    if(now_x + move[d][0] < 0 or now_x + move[d][0] >= n or now_y + move[d][1] < 0 or now_y + move[d][1] >= n or snail[now_y+move[d][1]][now_x+move[d][0]] != 0):
        d = (d + 1) % 4
    now_y = now_y + move[d][1]
    now_x = now_x + move[d][0]
    now_num = now_num - 1

for i in range(n):
    for j in range(n):
        if(snail[i][j] == m):
            find_x = j
            find_y = i
        print(snail[i][j] , end = ' ')
    print()
print(find_y + 1,find_x + 1)