68)등산경로(DFS)

문제

지도가 주어지면 출발지에서 도착지로 갈 수 있는 등산 경로가 몇 가지 인지 구하는 프로그램을 작성하기

 

조건

마을 뒷산의 형태를 나타낸 지도는 N*N 구역으로 나뉘어져 있으며, 각 구역에는 높이가 함께 나타나 있습니다.

 

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

어떤 구역에서 다른 구역으로 등산을 할 때는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있도록 등산로를 설계하려고 합니다.

 

등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳입니다.

 

출발지와 목적지는 유일합니다.

 

제한사항

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

 

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

 

문제풀이

def go(x, y):
  global cnt
  
  if x==ex and y==ey:
    cnt+=1
  else:
    for k in range(4):
      xx=x+dx[k]
      yy=y+dy[k]

      if 0<=xx<N and 0<=yy<N and ch[xx][yy]==0 and board[xx][yy]>board[x][y]:
        ch[xx][yy]=1
        go(xx, yy)
        ch[xx][yy]=0

dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
N=int(input())
board=[[0]*N for _ in range(N)]
ch=[[0]*N for _ in range(N)]
max=-2147000000
min=2147000000
for i in range(N):
  tmp=list(map(int, input().split()))
  for j in range(N):
    if tmp[j]<min:
      min=tmp[j]
      sx=i
      sy=j
    if tmp[j]>max:
      max=tmp[j]
      ex=i
      ey=j
    board[i][j]=tmp[j]

ch[sx][sy]=1
cnt=0
go(0, 0)
print(cnt)