066 - 등산경로(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

 

▣ 출력예제 1

5

 

 

 

#import sys
#sys.stdin = open('in5.txt', 'rt')


def DFS(x1, y1):
    global cnt

    if x1 == ex and y1 == ey:
        cnt += 1
        # print(cnt)
        # for x in dis:
        #     print(x)
        return
    else:
        for i in range(4):
            x = x1+dx[i]
            y = y1+dy[i]
            if 0 <= x <= (n-1) and 0 <= y <= (n-1) and a[x][y] > a[x1][y1]:
                dis[x][y] = 1
                DFS(x, y)
                dis[x][y] = 0


if __name__ == '__main__':
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    dis = [[0] * n for _ in range(n)]
    cnt = 0
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    sx = 0
    sy = 0
    ex = 0
    ey = 0
    end = 0
    start = float('inf')

    # 저점과 고점을 찾는 부분.
    for i in range(n):
        for j in range(n):
            if a[i][j] < start:
                start = a[i][j]
                sx = i
                sy = j
            if a[i][j] > end:
                end = a[i][j]
                ex = i
                ey = j

    # for x in a:
    #     print(x)
    # print(f'start:{sx},{sy} end:{ex},{ey}')

	# 시작점(저점)을 임의숫자로 표시함
    dis[sx][sy] = 8
    DFS(sx, sy)
    print(cnt)