[인프런] 등산경로

---

문제설명

등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있다. 마을 뒷산의 형태를 나타낸 지도는 N by N 구역으로 나누어져 있으며, 각 구역에는 높이가 함께 나타나 있다. 만약 N=5 라면, 아래와 같이 표현된다.

 

 

어떤 구역에서 다른 구역으로 등산할 때는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있도록 등산로를 설계하려고 한다. 등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳이다. 출발지와 목적지는 유일하다. 지도가 주어지면 출발지에서 도착지로 갈 수 있는 등산 경로가 몇 가지 있는지 구하는 프로그램을 작성해라.

입려조건

• 첫 줄에 N(5 <= N <= 13)이 주어지고, 다음 줄부터 N by N 의 지도정보가 N줄에 걸쳐 주어진다.

출력조건

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

사고과정

• 처음에 문제를 잘 못 읽어서 삽질을 많이 했다.. 이동할 때, 현재 있는 구역보다 높은 곳으로 갈 수 있다는 것인데, 현재 있는 구역 제외하고 현재 있는 구역의 상,하,좌,우 중 가장 높은 구역으로만 이동이 가능하다고 읽었다.. 문제도 제대로 파악하지 못하니... 반성해야 한다..
• 위 사실을 깨닫고 구현하는 데는 오래 걸리지 않았다.. 앞으로 문제를 제대로 읽자!
• 강의 풀이와 약간 달랐던 점은 최소, 최대 높이를 갖는 좌표를 구해야 하는데, 강의에서는 지도정보가 주어질 때, 해당 좌표들을 구했지만 나는 입력을 다 받고 난 후에 구했다.. 전자가 시간복잡도에서 좀 더 괜찮지 않을까 해서 전자 풀이를 더 선호하려 한다..!

풀이

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
# 시작, 도착 위치 찾아내기
min_x = min_y = max_x = max_y = -1
min_val = int(1e8)
max_val = -int(1e8)
for i in range(0, n):
    for j in range(0, n):
        if board[i][j] < min_val:
            min_val = board[i][j]
            min_x, min_y = i, j
        if board[i][j] > max_val:
            max_val = board[i][j]
            max_x, max_y = i, j
# 시작 위치 방문처리
visited[min_x][min_y] = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 0

def dfs(x, y):
    global cnt
    if x == max_x and y == max_y:
        cnt += 1
    else:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
                if board[nx][ny] > board[x][y]:
                    visited[nx][ny] = 1
                    dfs(nx, ny)
                    visited[nx][ny] = 0
dfs(min_x, min_y)
print(cnt)

- 입력받으면서 최대, 최소 좌표 구하기

n = int(input())
visited = [[0] * n for _ in range(n)]
# 시작, 도착 위치 찾아내기
min_val = int(1e8)
max_val = -int(1e8)
board = [[0] * n for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(n):
        if tmp[j] < min_val:
            min_val = tmp[j]
            min_x, min_y = i, j
        if tmp[j] > max_val:
            max_val = tmp[j]
            max_x, max_y = i, j
        board[i][j] = tmp[j]

# 시작 위치 방문처리
visited[min_x][min_y] = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 0

def dfs(x, y):
    global cnt
    if x == max_x and y == max_y:
        cnt += 1
    else:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
                if board[nx][ny] > board[x][y]:
                    visited[nx][ny] = 1
                    dfs(nx, ny)
                    visited[nx][ny] = 0
dfs(min_x, min_y)
print(cnt)