정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.
트리를 활용해서 값을 채우고, 트리를 배열로 변환하여 반환하는 방식으로 해결하였습니다. 구조가 사각형으로 바뀌어서 그렇지 결국 트리의 형태를 보여주고 있기 때문에 트리로 해결하는 것이 가장 적합해보였습니다.
풀이
1. 높이가 N인 트리를 생성합니다 (build_tredd) -> 문제에서 주어진 N도 높이를 의미하고 있기 때문에 필요한 노드의 수 만큼 생성됩니다.
2. 맨 위의 노드부터 시작해서 노드를 연결해나갑니다.아래 -> 오른쪽 -> 대각선 방향으로 이동하면서 자식 노드를 연결합니다.
3. 노드가 전부 생성되고, 연결되었으면 값을 채워나갑니다. visited를 사용해 방문한 노드인지 체크하고, 방문한 노드의 값을 증가시키면서 순차적으로 방문합니다.
4. 노드를 순환하면서 배열로 변환합니다.
class Node:
def __init__(self, x, y, value=0):
self.x = x
self.y = y
self.value = value
self.children = []
def build_tree(n):
root = Node(0, 0, 1)
nodes = [[None for _ in range(i + 1)] for i in range(n)]
nodes[0][0] = root
for i in range(n):
for j in range(i + 1):
if nodes[i][j] is None:
continue
# 아래로 이동
if i + 1 < n:
if nodes[i + 1][j] is None:
nodes[i + 1][j] = Node(i + 1, j)
nodes[i][j].children.append(nodes[i + 1][j])
# 오른쪽으로 이동
if j + 1 <= i:
if nodes[i][j + 1] is None:
nodes[i][j + 1] = Node(i, j + 1)
nodes[i][j].children.append(nodes[i][j + 1])
# 대각선 상향 이동
if i + 1 < n and j + 1 <= i:
if nodes[i + 1][j + 1] is None:
nodes[i + 1][j + 1] = Node(i + 1, j + 1)
nodes[i][j].children.append(nodes[i + 1][j + 1])
return root
def fill_values(root, n):
count = 1
queue = [root]
visited = set()
while queue:
current = queue.pop(0)
if (current.x, current.y) not in visited:
current.value = count
count += 1
visited.add((current.x, current.y))
queue.extend(current.children)
def tree_to_array(root, n):
result = [[0] * (i + 1) for i in range(n)]
queue = [root]
visited = set()
while queue:
current = queue.pop(0)
if (current.x, current.y) not in visited:
result[current.x][current.y] = current.value
visited.add((current.x, current.y))
queue.extend(current.children)
return sum(result, [])
def solution(n):
root = build_tree(n)
fill_values(root, n)
return tree_to_array(root, n)
트리를 사용하지 않는 경우 아래처럼 이전에 옮겨온 위치로 다음 경로를 판단하는 방법도 있습니다. 이동하던 도중 다음 위치가 벗어나거나 이미 값이 채워져 있는 경우 방향을 전환합니다. 이 방식은 위 코드에 비해 코드가 직관적이지 않지만 노드를 활용하지 않고 배열을 직접 사용하기 때문에 메모리 사용 측면에서 더 경제적이라 생각이 듭니다.
def solution(n):
answer = [[0] * (i + 1) for i in range(n)]
count = 1
current = [0, 0]
directions = ['down', 'right', 'up-left']
direction_index = 0
while count <= n * (n + 1) // 2:
answer[current[0]][current[1]] = count
count += 1
# 현재 방향에 따라 다음 위치 계산
if directions[direction_index] == 'down':
next_row, next_col = current[0] + 1, current[1]
elif directions[direction_index] == 'right':
next_row, next_col = current[0], current[1] + 1
elif directions[direction_index] == 'up-left':
next_row, next_col = current[0] - 1, current[1] - 1
# 다음 위치가 범위를 벗어나거나 이미 채워져 있는 경우 방향 전환
if not (0 <= next_row < n and 0 <= next_col <= next_row) or answer[next_row][next_col] != 0:
direction_index = (direction_index + 1) % 3 # 방향 전환
if directions[direction_index] == 'down':
next_row, next_col = current[0] + 1, current[1]
elif directions[direction_index] == 'right':
next_row, next_col = current[0], current[1] + 1
elif directions[direction_index] == 'up-left':
next_row, next_col = current[0] - 1, current[1] - 1
current = [next_row, next_col]
return sum(answer,[] )
