[알고리즘] 등산경로(DFS)

(문제) 등산경로(DFS)

---

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

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

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

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

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

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

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

입력설명

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

출력설명

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

테스트케이스

입력예제	출력예제
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	5
5 1 27 309 126 384 178 104 75 298 176 76 136 201 386 224 261 365 254 344 364 341 408 302 394 414	3
3 4 7 5 5 3 8 9 6 5	2
6 2 23 92 78 93 100 59 50 48 90 80 101 30 53 70 75 96 102 94 91 82 89 93 103 97 98 95 96 100 104 102 103 104 105 106 107	26
7 2 23 92 78 93 100 34 59 50 48 90 80 101 45 30 53 70 75 96 102 56 94 91 82 89 93 103 76 97 98 95 96 100 104 123 102 103 104 105 106 107 23 23 45 76 34 87 100 34	10
10 2 23 92 78 93 100 34 1 3 5 59 50 48 90 80 101 45 5 3 8 30 53 70 75 96 102 56 23 45 12 94 91 82 89 93 103 76 76 54 32 97 98 95 96 100 104 123 76 54 32 102 103 104 105 106 107 23 87 98 87 23 45 76 34 87 125 34 88 99 77 56 88 99 105 106 107 23 87 98 87 102 103 104 105 106 107 23 87 98 99 33 103 104 105 106 107 23 87 98 11	9

---

해결방법

1. 상, 하, 좌, 우를 나타내는 x좌표와 y좌표를 가지는 리스트를 생성
2. 등산 좌표에서 가장 작은 값과 가장 큰 값을 찾아서 출발지와 도착지를 결정한다
3. 출발지에서 시작하여 상, 하, 좌, 우 전부다 돌아서 현재 위치보다 큰 값으로만 갈 수 있도록 설정한다
4. 들렸던 곳은 가지 못하도록 체크리스트를 만들어서 돌 때마다 체크리스트에 체크를 한다.
5. 도착지에 도착했을 때 count 를 하나 더한다.

---

코드

def DFS(L, x, y):
    global count
    # 만약 도착지에 좌표가 도달 했을 경우
    if x == end_coor[0] and y == end_coor[1]:
        count = count + 1
        return
    else:
        for i in range(4):
            # 좌표 안에 있을 경우
            if 0 <= x + dx[i] < n and 0 <= y + dy[i] < n:
                # 안 들린 곳만 가기
                if ch_way[x + dx[i]][y + dy[i]] == 0:
                    # 전 보다 더 높은 곳
                    if way[x + dx[i]][y + dy[i]] > way[x][y]:
                        # 처음 들리기 때문에
                        ch_way[x + dx[i]][y + dy[i]] = 1
                        DFS(L+1, x + dx[i], y + dy[i])
                        # 갔다 왔기 때문에
                        ch_way[x + dx[i]][y + dy[i]] = 0

n = int(input())

way = [list(map(int,input().split())) for _ in range(n)]

ch_way = [[0] * n for _ in range(n)]

# 상우하좌
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

# 더 높은 구역에만 이동
# 출발지와 목적지는 유일 (가장 작은곳 출발지, 가장 큰 곳 목적지)

# 출발지, 목적지 초기화 하기 위한 설정
start = 2147000000
start_coor = [0, 0]

end = -2147000000
end_coor = [0, 0]

# 출발지, 목적지 찾기
for i in range(n):
    for j in range(n):
        if start > way[i][j]:
            start = way[i][j]
            start_coor = [i, j]

        if end < way[i][j]:
            end = way[i][j]
            end_coor = [i, j]

# 첫번째 시작 길 체크하기
ch_way[start_coor[0]][start_coor[1]] = 1

# 몇개의 길이 있는지 구하기
count = 0

# DFS 시작
DFS(0, start_coor[0], start_coor[1])

print(count)