登山経路(DFS)

9665 ワード
Pythonアルゴリズム解題 テキストリンク

深度/幅優先ナビゲーション(DFS、BFS)による


に質問


登山経路(DFS)


山登りが大好きなチョルスは、村の裏山で登山コースの計画を立てている.村の裏山の形を示す地図はN*Nエリアに分かれており、各エリアの高さが一緒に表示されています.
N=5は、以下のように表される.

あるエリアから別のエリアに山を登ると、そのエリアの上、下、左、右の中でより高いエリアにしか移動できないように登山ルートを設計してみます.登山道の起点は地域全体で最も低く、目的地は最も高い場所です.出発地と目的地は唯一です.
地図があれば、出発地から目的地までの登山ルートを尋ねるプログラムを作成してください.
■説明の入力
1行目は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

コード#コード#💻

'''
DFS는 백트래킹과 관련이 있다. (이전 체크를 풀어야 함) 
BFS는 퍼져나가는 느낌, DFS는 한 방향으로 쭉 나가는 느낌
'''
import sys
#sys.stdin = open("input.txt", "rt")    # read text
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 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)
リファレンス
  • インフラストラクチャ:Pythonアルゴリズム回答
    • [Python]ベース構文
    ThreadLocalの復号化