[인프런 | 파이썬 알고리즘] 등산경로(DFS, 높은곳만 이동, 출발지-목적지)

등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있습니다. 마을 뒷산의 형태를 나타낸 지도는 N*N 구역으로 나뉘어져 있으며, 각 구역에는 높이가 함께 나타나 있습니다.

N=5이면 아래와 같이 표현됩니다.

어떤 구역에서 다른 구역으로 등산을 할 때는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있도록 등산로를 설계하려고 합니다. 등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳입니다. 출발지와 목적지는 유일합니다.
지도가 주어지면 출발지에서 도착지로 갈 수 있는 등산 경로가 몇 가지 인지 구하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 N(5<=N<=13)주어지고, N*N의 지도정보가 N줄에 걸쳐 주어진다.

▣ 출력설명
등산경로의 가지수를 출력한다.

▣ 입력예제 1
5
2 23 92 78 93
59 50 48 90 80
30 53 70 75 96
94 91 82 89 93
97 98 95 96 100

 

 

문제풀이

출발지는 map_data의 최소값

도착지는 map_data의 최대값

top, right, bottom, left 중 현재 값보다 큰 쪽으로만 이동

출발지에서 도착지까지 가는 경우의 수 구하기

 

문제해결

1. 입력 받을 때 출발지(최소값), 목적지(최대값) 갱신하면서 구하기

2. 출발지 visite_list 방문처리

3. DFS(출발지x좌표, 목적지y좌표) 시작

4. 4방향 돌면서 범위에 벗어나지 않도록 and 현재 값보다 큰 경우에만 다음 방문

5. 목적지 좌표에 도달한 경우 카운트 증가

def DFS(current_x, current_y, end_x, end_y, n) :
    global map_data
    global visite_list
    global count

    dx = [-1, 0, 1, 0]          #위쪽 0, 오른쪽 1, 아래 2, 왼쪽 3
    dy = [0, 1, 0, -1]
    
    #목적지 x, y에 도달하는 경우, 방법의 수 카운트
    if current_x == end_x and current_y == end_y :
        count += 1
    else :
        for d in range(4) :
            next_x = current_x + dx[d]
            next_y = current_y + dy[d]

            #x좌표, y좌표는 범위 내 and 방문하지 않은 경우(visite_list[next_x][next_y] is False)
            #top, right, bottom, left 중 현재 값보다 큰 경우에만 다음 방문
            if 0 <= next_x <= (n-1) and 0 <= next_y <= (n-1) and visite_list[next_x][next_y] is False and map_data[next_x][next_y] > map_data[current_x][current_y] :
                visite_list[next_x][next_y] = True
                DFS(next_x, next_y, end_x, end_y, n)
                visite_list[next_x][next_y] = False

def solution() :
    global map_data
    global visite_list
    global count

    n = int(input())
    
    map_data = [[0] * n for _ in range(n)]
    visite_list = [[False] * n for _ in range(n)]

    min = 2147000000
    max = -2147000000
    count = 0
    
    for i in range(n) : 
        line = list(map(int, input().split()))    
        for j in range(len(line)):
            if line[j] < min :
                min = line[j]           #출발지 최소값 x좌표, y좌표 찾기
                start_x = i
                start_y = j
            if line[j] > max :          #목적지 최대값 x좌표, y좌표 찾기
                max = line[j]
                end_x = i
                end_y = j
            map_data[i][j] = line[j]

    visite_list[start_x][start_y] = True
    DFS(start_x, start_y, end_x, end_y, n)
    print(count)


solution()