[재귀함수] 실습 문제 풀기6 (격자이동)

문제 설명

DFS

깊이 우선 탐색. 재귀함수의 형태로 알고리즘을 구성하는 것이 일반적이며, 순서의 상관없이 모든 노드를 방문하려 하는 경우에 유용하게 사용할 수 있다.

단, DFS의 경우 구해진 해가 최적의 해라는 보장이 없다.

위의 문제의 경우 연결된 노드들 모두를 다 확인하고 넘어가는 것이 아니라 끝까지 도달하는 경로를 알아야 하기 때문에 DFS로 접근해야 한다.

DFS 기본 Format

기본형식

def dfs(graph, visited, start):
    visited[start] == True
    
    for i in graph[start]:
        if not visited[i]:
            dfs[graph, visited, i]

2차원 배열인 경우

이때 여러가지 방법이 있는데 나는 아래와같은 구조를 선호한다.

• x, y 대신 row, col로 표현. >> 나중에 이중 for문 도는 경우에 착각하는 경우가 존재
• 다음 재귀문 호출 하는경우 불가능 한 조건을 위에 명시적으로 표현
• 미리 방문 처리 (문제중에 미리 방문처리를 해야 유리한 경우가 존재)

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))