[파이썬 알고리즘 문제풀이] - Section7 / 깊이/넓이 우선 탐색(DFS, BFS) 활용 - 11

등산경로(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("input.text", "rt")
from collections import deque

n = int(input())
g = [list(map(int, input().split())) for _ in range(n)] #nxn 2차원 리스트

min_data = 24242424
max_data = -24242424
x,y = 0,0
for i in range(n):
    for j in range(n):
        if g[i][j] < min_data:
            min_data = g[i][j]
            x,y = i,j #시작 위치
        if g[i][j] > max_data:
            max_data = g[i][j]


dx = [1,-1,0,0]
dy = [0,0,1,-1]

ch = [[0] * n for _ in range(n)] #중복 체크
ch[x][y] = 1 
cnt = 0
def DFS(x,y):
    global cnt
    if g[x][y] == max_data: #목적지 종료조건.
        cnt += 1
    else: #아직 도착전이면 계속 가지 뻗기
        for i in range(4):
            nx = x + dx[i]
            ny = y  +dy[i]

            if 0<=nx<n and 0<=ny<n:
                if ch[nx][ny] == 0: #방문 전
                    if g[nx][ny] > g[x][y]: #현재 위치보다 높은 곳으로
                        ch[nx][ny] = 1
                        DFS(nx,ny)
                        ch[nx][ny] = 0 #백트랙킹
    
DFS(x,y)
print(cnt)

코멘트

경로 가짓수 문제. 보자마자 DFS로 출발점부터 끝점까지 가야한다는 것을 이해했다면 쉽게 DFS로 접근했을 것이다.