[Implementation] 백준 1913번 “달팽이” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/1913

풀이

• 외각의 크기에 따라, 가운데 좌표를 시작점으로 상하좌우로 이동하는 횟수를 일반화할 수 있습니다.
  • 시작점을 기준으로, 진행순서는 상 → 우 → 하 → 좌 → 상이며,
  • 진행횟수는 n에 따라, 상 n번, 우 n-2번, 하 n-1번, 좌 n-1번이 됩니다.
• 또한, 진행하고 있는 외각의 크기에 따라 시작점이 항상 (n//2, n//2) 이 될 수 있도록 n을 조절해야합니다.
  • 예를 들어, n이 7로 주어진다면,
  • 현재 진행하고 있는 외각이 변경됨에 따라
  • 시작좌표를 (3, 3) → (2, 2) → (1, 1)로 변경해야합니다.
• 세부 알고리즘은 아래 코드와 같습니다.

코드

import sys

# 자연수 N 입력
n = int(sys.stdin.readline())

# 찾고자하는 자연수 입력
find = int(sys.stdin.readline())

# 결과 그래프
graph = [[0]*(n) for _ in range(n)]

# 상하좌우 이동 좌표
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 현재 시작 좌표 (중심점)
x, y = n//2, n//2
# 중심점에 번호 할당
graph[x][y] = 1

# 시작 번호
num = 2
# 시작 외각 크기
size = 3

# 현재 좌표가 표를 다 돌아, 0, 0이 될때까지
while (x != 0 or y != 0):

    # 번호가 현재 외각의 크기만큼 할당될때까지
    while (num <= size * size):

        # 현재 좌표가 현재 외각의 시작 좌표라면, 상으로 이동
        if (x == y == (n//2)):
            # 상우하좌로 이동해야하는 횟수 저장
            up, right, down, left = size, size-2, size-1, size-1
            # 상으로 이동
            x += dx[0]
            y += dy[0]
            # 상으로 이동해야하는 횟수 감소
            up -= 1

        # 우하좌상 이동 횟수가 남아있다면 이동
        elif (right > 0):
            x += dx[3]
            y += dy[3]
            right -= 1
        elif (down > 0):
            x += dx[1]
            y += dy[1]
            down -= 1
        elif (left > 0):
            x += dx[2]
            y += dy[2]
            left -= 1
        else:
            x += dx[0]
            y += dy[0]
            up -= 1

        # 현재 좌표에 번호 할당
        graph[x][y] = num
        num += 1

    # 현재 외각에 대한 번호 할당이 끝났으므로, 
    # 외각의 크기를 변경하고
    size += 2
    # 시작 좌표 변경을 위해 n 수정
    n -= 2

# 찾고자하는 값의 위치
find_x, find_y = -1, -1

# N개의 줄에 걸쳐 표를 출력
for i in range(len(graph)):
    for j in range(len(graph)):
        if (graph[i][j] == find):
            find_x, find_y = i, j
        print(graph[i][j], end = " ")
    print("")

# 찾고자하는 값의 위치 출력
print(find_x + 1, find_y + 1)

참고

• https://velog.io/@hygge/Python-백준-1913-달팽이-Brute-Force