문제
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
풀이과정_bfs
- 삼각형을 행렬로 변환시킨다.
7 7 -1 -1 -1 -1 3 8 3 8 -1 -1 -1 8 1 0 --> 8 1 0 -1 -1 2 7 4 4 2 7 4 4 -1 4 5 2 6 5 4 5 2 6 5 visit배열을 만들어서,visit값이 0인 경우에는matrix[nx][ny] + visit[x][y], 0이 아닌 경우에는 현재visit의 값과matrix[nx][ny]+ visit[x][y]중 더 큰 값을 대입한다.
소스코드
소요 시간 26:44 (dfs로 시간 초과 겪고 bfs로 바꿈..)
# 대각선 아래로 한칸 오른쪽, 한칸 왼쪽
dx = [1,1]
dy = [0,1]
def bfs(matrix, height, i, j):
visit = [[0] * height for _ in range(height)]
visit[0][0] = matrix[0][0]
q = [(i,j)]
while q:
x,y = q.pop(0) #인덱스
for i in range(2):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < height and 0 <= ny < height and matrix[nx][ny] != -1:
if not visit[nx][ny]:
visit[nx][ny] = matrix[nx][ny] + visit[x][y] #누적합
q.append((nx, ny))
else:
visit[nx][ny] = max(matrix[nx][ny] + visit[x][y], visit[nx][ny])
return max(visit[len(visit)-1])
def solution(triangle):
height = len(triangle)
triangle_matrix = []
for t in triangle:
size = height - len(t) #추가해야할 -1의 개수
for _ in range(size):
t.append(-1)
triangle_matrix.append(t)
answer = bfs(triangle_matrix, height, 0, 0)
return answer추가 풀이과정_dfs
dfs도 위 풀이와 비슷한 방법이지만, dfs에서는 마지막 노드에 도달했을 때, answer을 max 값으로 업데이트 해주었다. 또한 visit 배열을 방문 표시 목적으로 사용하며, dfs를 빠져나왔을 때엔 다시 이전 노드로 되돌아갈 수 있도록 visit을 0으로 바꾸어준다.
** dfs로 해결하면 시간 초과 발생함!
추가 소스코드_dfs
# 대각선 아래로 한칸 오른쪽, 한칸 왼쪽
dx = [1,1]
dy = [0,1]
answer = 0
def dfs(matrix, visit, height, x, y, total):
if x == height - 1: #마지막 노드에 도달했을 때
global answer
total += matrix[x][y]
answer = total if total > answer else answer #더 큰 값으로 업데이트
else:
for i in range(2):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < height and 0 <= ny < height and matrix[nx][ny] != -1 and not visit[nx][ny]:
visit[nx][ny] = 1
dfs(matrix, visit, height, nx, ny, total+matrix[x][y])
visit[nx][ny] = 0
def solution(triangle):
height = len(triangle)
triangle_matrix = []
for t in triangle:
size = height - len(t) #추가해야할 -1의 개수
for _ in range(size):
t.append(-1)
triangle_matrix.append(t)
visit = [[0] * height for _ in range(height)]
visit[0][0] = 1
dfs(triangle_matrix, visit, height, 0, 0, 0)
return answer
print(solution([[1],[2,3],[4,5,6]])) #30