[#1913] 달팽이

문제

#1913 달팽이
Silver3
적용 알고리즘: Implementation 알고리즘

---

풀이 방법

• 숫자의 위치는 사용자가 어떤 숫자를 입력하던지간에 1에서 시작하며, 그 위치는 동일하다. 즉, 좌표 위치를 아는 1부터 시작하여 숫자를 하나씩 증가시키며 보드를 채운다.
• 하나의 예시를 가지고 규칙을 찾고 이를 일반화한다.
• “방향”을 사용한다. 중앙(1)을 기준으로 u -> r -> d -> l 순서로 방향이 비뀐다.
• 방향이 바뀌게 되는 모서리 숫자의 간격으로 규칙을 찾는다.

예시를 통한 일반화 / 규칙 찾기

• 사용자가 7를 입력하면, 모서리의 숫자는 1, 2, 3, 5, 7, 10, 13, 17, 21, 26, 31, 37, 43이다.
• 이들의 간격은 처음부터 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6이다. 즉, 모퉁이를 두 번째 돌 때마다 한 변에 있는 숫자가 하나 증가한다.

변수 설정

• repet: 모퉁이를 몇번 돌았는가를 저장하는 변수. 0, 1, 2의 값을 가지며 2일 경우 count가 하나 증가한다.
• count: 한 방향에 몇 개의 숫자가 놓여야 하는지 저장하는 변수
• dir: 숫자의 진행 방향을 저장하는 변수. “u”, “r”, “d”, “l”의 순서로 방향이 돌아간다.
• till_cnt: 현재 이 방향으로 몇번 진행하였는지 저장하는 변수. 매 코너를 돌 때마다 초기화된다.
• col, row: 숫자가 놓일 위치. 보드의 정중앙으로 초기화된다.

코드 흐름

1. 현재 위치에 값을 넣고, 값을 넣었으니 till_cnt를 1 증가시킨다.
2. 현재 이 모서리에 놓은 수의 개수(till_cnt)와 놓여야 될 수(count)를 비교한다. 같은 경우, 모서리에 도달했다는 의미이므로 방향(dir)을 바꾸어주고, 한 변이 끝났으므로 repet를 1 증가시키고, till_cnt를 0으로 초기화한다.
   • 만일 repet가 2라면, 그 다음 모서리에서는 출력해야 할 수 가 하나 증가하므로 count를 1 증가시킨다.
3. 2에서 만약 같지 않은 경우, 현재는 모서리가 아닌 변의 한 지점에 있다는 의미이므로 저장된 방향(dir)을 바탕으로 그 다음에 놓일 위치(좌표)를 업데이트 해준다.
4. 좌표 (0, 0)지점을 사용자가 입력한 값의 제곱으로 채운다.

코드

n = int(input())
k = int(input())

board = [[0 for _ in range(n)] for _ in range(n)]

repet = 0
count = 1
dir = "u"
col, row = n // 2, n //2
till_cnt = -1

for num in range(1, n ** 2):
    board[col][row] = num
    till_cnt += 1

    # 자리 체인지
    if (till_cnt == count):
        # 모서리에 도달하였으므로 방향 전환
        if (dir == "u"):
            dir = "r"
        elif (dir == "r"):
            dir = "d"
        elif (dir == "d"):
            dir = "l"
        elif (dir == "l"):
            dir = "u"

        repet += 1

        if (repet == 2):
            count += 1
            repet = 0

        till_cnt = 0
    
    # 그 다음 자리로 이동
    if (dir == "u"):
        col -= 1
    elif (dir == "r"):
        row += 1
    elif (dir == "d"):
        col += 1
    elif (dir == "l"):
        row -= 1

board[0][0] = n**2

x, y = 0, 0

for i in range(n):
    for j in range(n):
        if (board[i][j] == k):
            x, y = i, j
        print(board[i][j], end=" ")
    print()
print(x + 1, y + 1)

체감 난이도: 4.7/5
문제를 볼 때까지는 대체 구현 알고리즘이 뭐지.. 했는데 이 문제를 보고 확실히 알게 된 것 같다. 머릿속에서는 간단하게 ‘아, 이렇게 하면 되겠구나’ 했는데 코드로 구현하는 과정이 꽤나 까다로웠다. 구현을 어느정도 했을 때 count 변수에서 착오가 있어서 한참동안 디버깅을 하고 고민했는데 해당 변수에서 나머지 변수와의 관계를 연쇄적으로 생각하는 것도 도움이 된 것 같다. 솔직히 Silver3 보다는 어려운 난이도인 것 같다.

• count가 언제 증가? -> repet가 2가 되었을 때
• repet가 언제 증가? -> 방향(dir)이 바뀔 때마다
• 방향이 언제 바뀜? -> till_cnt 이 count가 될 때
• till_cnt가 언제 증가? -> 숫자를 놓는 매 순간마다