파이썬 알고리즘 065 | 등산경로(DFS)

65. 등산경로(DFS)

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

<내 풀이>

• 일단 코드를 구현하다가 막힌 첫번째 구간 :
  min과 max를 구하긴 했는데 얘네의 a에서의 자리 (a[i][j])가 어딘지 어떻게 구하지
  => min이랑 max가 지정될 때 그때의 i,j를 저장하면 됨

def dfs(x,y):
    global cnt
    if x==max1 and y==max2:
        cnt+=1
        return
    else :
        max=0
        for i in range(4) :
            xx=x+dx[i]
            yy=y+dy[i]
            if 0<=xx<=n-1 and 0<=yy<=n-1 and a[xx][yy]>a[x][y]: 
                dfs(xx,yy)
if __name__=='__main__' :
    n=int(input())
    a=[list(map(int,input().split())) for _ in range(n)]
    max=-1 #목적지
    min=101 #출발지
    for i in range(n):
        for j in range(n):
            if a[i][j] > max:
                max=a[i][j]
                max1=i
                max2=j
            if a[i][j]<min: 
                min=a[i][j]
                min1=i
                min2=j
    cnt=0
    dx=[-1,0,1,0]
    dy=[0,1,0,-1]
    dfs(min1,min2)
    print(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 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
                DFS(xx, yy)
                ch[xx][yy]=0

if __name__=="__main__":
    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
    DFS(sx, sy)
    print(cnt)

<반성점>

<배운 점>

• 좀 더 쉬운 2차원 리스트에서 최대, 최솟값 찾기
  :maxnumber=max(map(max, list))
  :minnumber=min(map(min, list))

• 2차원 리스트 안에서 어떤 값의 인덱스 번호 찾기 (a[i][j] 형식으로)

for i in range(n):
        for j in range(n):
            if a[i][j] > max:
                max=a[i][j]
                max1=i
                max2=j

=>여기서 오래 헤맸었음

• 다른 분이 인덱스 번호를 찾은 방법

s=min(map(min,lst))
s=[(i,j) for i in range(n) for j in range(n) if lst[i][j]==s]
e=max(map(max,lst))
e=[(i,j) for i in range(n) for j in range(n) if lst[i][j]==e]
dfs(s[0])

print(cnt)