삼각 달팽이

날짜 : 2023. 10. 03

사용 언어 : python

 

문제

 

 

코드

def solution(n):
    tri = [[-1] * 1001 for _ in range(1001)]
    for i in range(n):
        for j in range(i + 1):
            tri[i][j] = 0
    r, c, d = 0, 0, 0
    dx  = [1, 0, -1]
    dy = [0, 1, -1]
    tri[r][c] = 1  # 시작점
    cnt = 1
    while cnt < (n * (n + 1) // 2):
        cnt += 1  # 카운트 증가
        nx = r + dx[d]  # 다음 좌표
        ny = c + dy[d]
        if tri[nx][ny] != 0:  # 이미 접근했거나 범위를 이탈
            d = (d + 1) % 3  # 방향 전환
            nx = r + dx[d]  # 적용
            ny = c + dy[d]
        tri[nx][ny] = cnt  # 이동거리 최신화
        r = nx  # 이동좌표 최신화
        c = ny
        # print(r, c, cnt, d)
    res = []
    for i in range(n):
        for j in range(i+1): 
            res.append(tri[i][j])  # 각 row별로 삽입
    return res

 

 

풀이

- n의 최대값이 1000이기 때문에 먼저 그래프에 대해 1001 * 1001 그래프를 만들고, 각 원소를 전부 -1로 설정

- 그 다음 삼각형의 값만 알 수 있게 해당 범위만 0으로 만든 후 달팽이 방향으로 돌린다.

- 달팽이 패턴에서 방향은 총 3개가 있고 기준을 (i, j)로 잡았을 때, 좌측 하단으로 가는 (i + 1, j)와 우측으로 이동하는 (i, j + 1), 그리고 좌측 상단으로 이동하는 (i - 1, j - 1) 이렇게 3가지가 있다.

- 해당 방향은 각각 dx, dy 리스트를 만들어서 구현했고, 맨 처음 지점은 (0, 0)에 위치는 1로 설정한다.

- 그리고 이동하는 거리는 총 n * (n + 1) // 2이기 때문에 탈출조건을 다음과 같이 설정한다.

- 0이 아닌 값을 만나는 경우는 기존에 설정한 노드에 접근 or 범위 이탈이기 때문에 해당 케이스는 방향을 바꾼 다음 다시 이동하는 것으로 구현한다.

- while문을 다 돌린 다음 0으로 설정한 경우와 동일하게 결과용 리스트에 원소를 넣고 해당 리스트를 리턴한다.

 

알게된 점

- 맨 처음 삼각형의 형태로만 0으로 설정해서 데이터를 넣으려다보니 이탈하는 케이스를 확실하게 구현하기 어려웠다.

- 그래서 n의 최댓값인 1000보다 큰 1001 * 1001로 설정해서 해당 문제를 해결했다.

- 그 다음은 이탈하는 케이스를 걸러내면서 단순 -1인 경우만을 넣다보니 이전에 설정한 값이 덮어씌워지는 경우도 발생했다.
- 그래서 단순 tri[nx][ny] == -1일때만 방향을 바꾸기보다는 0이 아닐 때, 즉 이전에 접근했거나 범위를 이탈했을 때를 아우르는 케이스로 설정해서 문제를 해결할 수 있었다.

- 구현 자체는 어렵지 않았지만 자잘한 부분에서 발생하는 요소들을 해결하려다보니 꽤 고민을 했었다.

 

 

참고 사이트

-