💻 문제: 달팽이

문제 소개 🧐

홀수 N이 주어졌을 때, 1부터 N²까지의 자연수를 달팽이 모양으로 N×N 표에 채우고, 특정 숫자의 좌표를 찾는 문제다.

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 24832 10898 8115 45.414%

입력 📝

  • 첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다.
  • 둘째 줄에는 위치를 찾고자 하는 N² 이하의 자연수가 하나 주어진다.

출력 📤

  • N개의 줄에 걸쳐 표를 출력한다.
  • N+1번째 줄에는 입력받은 자연수의 좌표를 출력한다. (1-based index)

나의 풀이 ✨

Idea

달팽이가 움직이는 방향(아래, 오른쪽, 위, 왼쪽)에 따라 순차적으로 숫자를 채워나가는 시뮬레이션 방식을 사용했다.

  1. N x N 크기의 2차원 배열을 0으로 초기화한다.
  2. 가장 큰 수인 N*N부터 시작하여 1까지 숫자를 줄여가며 배열에 채운다.
  3. 움직이는 방향은 dir 변수를 이용해 0(아래), 1(오른쪽), 2(위), 3(왼쪽)으로 관리한다.
  4. 한 방향으로의 채우기가 끝나면 dir을 1 증가시켜 방향을 바꾼다.
  5. 한 바퀴(아래-오른쪽-위-왼쪽)가 모두 돌면, 탐색 범위를 안쪽으로 한 칸씩 좁힌다. (start += 1, end -= 1)
  6. 숫자를 채울 때마다 찾고자 하는 target 값인지 확인하고, 맞다면 좌표를 저장한다.

Code

import sys

N = int(sys.stdin.readline().rstrip())
target = int(sys.stdin.readline().rstrip())

def is_target(num):
    global target

    if num == target:
        return True
    else:
        return False

def snail():
    global N
    result = [[0 for _ in range(N)] for _ in range(N)]
    start = 0
    end = N-1
    num = N ** 2
    dir = 0
    pos = (0,0)

    while num > 0:
        dir %= 4
        if dir == 0:  # 아래로
            for r in range(start, end+1):
                result[r][start] = num
                if is_target(num):
                    pos = (r+1, start+1)
                num -= 1
                
        elif dir == 1:  # 오른쪽
            for c in range(start+1, end+1):
                result[end][c] = num
                if is_target(num):
                    pos = (end+1, c+1)
                num -= 1
        elif dir == 2:  # 위로
            for r in range(end-1, start-1, -1):
                result[r][end] = num
                if is_target(num):
                    pos = (r+1, end+1)
                num -= 1
        elif dir == 3:  # 좌로
            for c in range(end-1, start, -1):
                result[start][c] = num
                if is_target(num):
                    pos = (start+1, c+1)
                num -= 1
            # 끝났으니까 start, end 값 조정
            start += 1
            end -= 1

        dir += 1
    
    return pos, result

answer_pos, answer_list = snail()
for ans in answer_list:
    print(*ans)
print(*answer_pos)

Result

  • 결과: 성공! 🎉
  • 주어진 로직에 따라 N*N부터 1까지 숫자를 채워나가며 달팽이 배열을 완성했다.

배운 점 및 개선할 부분 🤔

  • 시뮬레이션의 정석: 이 문제는 방향과 경계를 정확하게 관리하는 것이 핵심인 대표적인 시뮬레이션 문제다. dir 변수로 방향을 제어하고, start와 end 변수로 배열의 채울 범위를 좁혀나가는 방식이 유효했다.
  • 좌표계 변환: 문제의 좌표는 1-based index이지만, 배열은 0-based index를 사용하므로 값을 저장하고 출력할 때 +1을 해주는 등 주의가 필요하다.
  • 시작 값: 숫자를 큰 값부터 채우는 방식으로 구현했다. 반대로 1부터 채워나갈 수도 있는데, 그 경우 시작 위치와 방향 전환 로직이 달라질 것이다. 어떤 방식이든 일관성 있게 구현하는 것이 중요하다.
  • 파이썬 내장 식별자: 생각해보니 dir은 파이썬의 내장 식별자였다. 더 큰 시스템을 만들 때를 대비해서라도 내장 식별자를 의식적으로 피하는 습관을 들여야겠다.

빙글빙글, 달팽이 배열을 만들다 보면 방향 감각과 경계 처리 능력이 쑥쑥 자란다.

⁂