파이썬 DFS 등산경로 문제

등산경로(DFS)

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

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

▣ 입력설명
첫 번째 줄에 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

---

간단한 문제다.

각각 위치한 곳에서 상하좌우를 탐색하고 자신이 가진 숫자보다 높은 숫자로 이동하며 탐색하면 된다.

주의 해야할 점은 이중 리스트로 담긴 구역정보를 탐색할 때 리스트 밖의 정보를 참조하지 않게 해야한다.

 

그리고 가장 낮은곳을 시작점으로 가장 높은곳을 끝점으로 찾기 위해서 

값을 입력함과 동시에 찾는다. 

한줄씩 리스트를 입력하기 때문에 min, max 를 변수에 담아 

입력되는 리스트에서 가장 작은 값과 큰값을 min max와 비교하며 담는다.

모든 입력이 끝나면 가장작은 값과 큰 값이 남는다. 

탐색한 경로를 표시하는 ch 배열을 생성해 1로 체크하며 탐색. 시작은 가장 낮은지점부터 탐색하며 끝점에 도달하면 

cnt 를 증가시킨다.

dx = [1,0,-1,0]
dy = [0,-1,0,1]
def DFS(x,y):
    global cnt
    if x == ex and y == ey :
        cnt += 1
    else:
        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            if  0<=xx<=n-1 and 0<= yy <= n-1 and ch[xx][yy] == 0  and arr[xx][yy] > arr[x][y]:
                ch[xx][yy] = 1
                DFS(xx,yy)
                ch[xx][yy] = 0

if __name__ == "__main__":
    n = int(input())
    arr = []
    ch = [ [0] * n for _ in range(n) ]
    min = 2147480000
    max = -2147480000
    for i in range(n):
        arr.append(list(map(int,input().split())))
        for idx,v in enumerate(arr[i]):
            if v < min:
                min = v
                sx = i
                sy = idx
            if v > max:
                max = v
                ex = i
                ey = idx
         
    ch[sx][sy] = 1
    cnt = 0
    DFS(sx,sy)
    print(cnt)