Algorithm - 등산 경로(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[등산 경로(DFS)]

 

등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있다.

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

N=5이면, 마을 뒷산의 형태를 나타낸 지도는 아래와 같이 표현된다.

 

5*5 격자판

 

어떤 구역에서 다른 구역으로 등산을 할 때에는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있다.

등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳이다. (단, 출발지와 목적지는 유일함)

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

 

 

*입력 설명

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

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_66.txt', 'rt')

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)
    
# 출력 : 5

 

input_66.txt(입력)

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. DFS 탐색은 시계방향으로 진행되며, 해당 문제에서는 격자판의 값이 높은쪽으로만 이동(탐색)할 수 있다.
2. 변수 board는 격자판의 정보를 입력하기 위한 리스트로 사용된다.
3. 변수 ch는 이미 지니간 경로를 체크하기 위한 리스트로 사용된다. (중복 탐색을 방지)
4. ch[xx][yy] = 1은 이미 지나간 경로를 체크하는 코드이고, ch[xx][yy] = 0은 이미 지나간 경로를 다시 되돌아오는 경우 체크를 지우기 위해 사용되는 코드이다. (0값으로 초기화)
5. 변수 sx(행), sy(열)는 시작점의 x좌표와 y좌표를 의미하며, 해당 좌표는 격자판의 최소값이다.
6. 변수 ex(행), ey(열)는 도착점의 x좌표와 y좌표를 의미하며, 해당 좌표는 격자판의 최대값이다.
7. ch[sx][sy] = 1 코드는 시작점의 좌표를 의미한다.
8. 변수 xx와 yy는 앞으로 진행할 DFS 탐색방향을 의미한다.