[BOJ/백준] 21923 곡예비행

import sys
from collections import deque
input = sys.stdin.readline


def bfs(point,dis_list,flag):
    dis_list[point[0]][point[1]] = arr[point[0]][point[1]]
    dx = [-1,0]
    dy = [0,1]

    stack = deque()
    stack.append((point[0],point[1]))

    while stack:
        x,y = stack.popleft()

        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]*flag
            if 0<=nx<N and 0<=ny<M:
                if dis_list[nx][ny] < dis_list[x][y] + arr[nx][ny]:
                    dis_list[nx][ny] = dis_list[x][y] + arr[nx][ny]
                    stack.append((nx,ny))
        


N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
INF =float('inf')
start_distance = [[-INF for _ in range(M)] for _ in range(N)]
end_distance = [[-INF for _ in range(M)] for _ in range(N)]

start_point = (N-1,0)
end_point = (N-1,M-1)
bfs(start_point,start_distance,1)
bfs(end_point,end_distance,-1)

max_value = -INF

for i in range(N):
    for j in range(M):
        if start_distance[i][j] + end_distance[i][j] > max_value:
            max_value = start_distance[i][j] + end_distance[i][j]
print(max_value)

 

 

 이 문제는 저는 BFS를 이용해서 풀었다.(근데 아직 푼사람이 적은지 solved.ac 기준에는 다이나믹 프로그래밍 밖에 없다.)

 

boj.kr/2206 문제와 비슷한 방식으로 풀었다.

 

 

이 문제를 봐보면 상승이나 하강은 특정한 방향으로 밖에 가지 못한다.

 

이 점을 이용해서 우리는 특정지점 (x,y)까지의 최대값을 bfs를 이용해 갱신할 수 잇을것이다.

 

 

그래서 나는 (N-1,0)에서 상승을 시작하므로, 이 지점을 시작으로 갈수 있는 모든지점에 대해, bfs를 돌려 최대값을 갱신을 해주었다.

 

똑같은 방식으로 (N-1,M-1) 위치로 하강을 해야하므로, 이 위치에서 하강의 반대방향으로 BFS를 돌리면서 최대값을 갱신을 해주었다.

 

그러면 우리는 상승을 할때의 각 지점의 최대값 하강을 할때의 각 지점의 최대값을 가지고 있는 행렬을 가지게 되었다.

 

이 두 행렬의 합을 전체 탐색을 하면서, 가장 큰 값을 출력해주면 되는 문제이다.