깊이 우선 탐색. 재귀함수의 형태로 알고리즘을 구성하는 것이 일반적이며, 순서의 상관없이 모든 노드를 방문하려 하는 경우에 유용하게 사용할 수 있다.
단, DFS의 경우 구해진 해가 최적의 해라는 보장이 없다.
위의 문제의 경우 연결된 노드들 모두를 다 확인하고 넘어가는 것이 아니라 끝까지 도달하는 경로를 알아야 하기 때문에 DFS로 접근해야 한다.
def dfs(graph, visited, start):
visited[start] == True
for i in graph[start]:
if not visited[i]:
dfs[graph, visited, i]
이때 여러가지 방법이 있는데 나는 아래와같은 구조를 선호한다.
dc = [1,0,-1,0]
dr = [0,1,0,-1]
def dfs(graph ,visited, row, col):
# 원하는 처리
for i in range(4):
new_r = row + dr[i]
new_c = col + dc[i]
if new_r < 0 or new_r >= H or new_c < 0 or new_c >= W: # index 넘어가는경우 실행 x
continue
if visited: # 이미 방문했다면 진행 x
continue
graph[new_r][new_c] = True # 방문처리
dfs(graph, visited, new_r, new_c)
일반 적인 재귀함수는 모든 계산이 끝나면 수식들이 한번에 계산 되어서 return되지만, 꼬리 재귀함수는 각각의 계산 결과를 꼬리표처럼 가지고 다니는 구조이다. 본 문제에서 꼬리 재귀함수를 이용하는 경우 목표 지점에 도달했을 때 복잡하게 값을 return 할것 없이 자신의 꼬리표를 return하여 해결 할 수 있다.
N = int(input())
M = [list(map(int,input().split()))for _ in range(N)]
visitied = [[True for _ in range(N)]for _ in range(N)]
dx = [1, 0]
dy = [0, 1]
answer = []
def dfs(graph, ret, start): # 꼬리 재귀함수로 구성
ret += graph[start[0]][start[1]]
if start == [N-1, N-1]: # 목표 지점에 도달하면
answer.append(ret) # 각각 목표 지점까지 도달하면서 게산된 값을 return
for i in range(2):
new_x = start[0] + dx[i]
new_y = start[1] + dy[i]
if new_x >=0 and new_x < N and new_y >=0 and new_y < N: # index 넘어가지 않는경우
dfs(graph, ret, [new_x, new_y])
dfs(M, 0, [0,0])
print(max(answer))