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

사용 언어: Python3

문제

풀이

내 풀이

import sys
sys.setrecursionlimit(10**6)

dx, dy = [0,-1,0,1], [1,0,-1,0]
def DFS(x, y):
    global cnt
    if (x, y) == end:
        cnt += 1
    else:
        for w in range(4):
            xx, yy = x+dx[w], y+dy[w]
            if xx<0 or xx>=N or yy<0 or yy>=N:
                continue
            if visited[xx][yy] == 1:
                continue
            if board[x][y] >= board[xx][yy]: # ✅ 더 높은 구역으로만 이동 가능
                continue
            visited[xx][yy] = 1
            DFS(xx, yy)
            visited[xx][yy] = 0 # ✅ back

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

# init start, end
mn = min(map(min, board)) # ✅ 2차원 리스트에서 최솟값 구하기
mx = max(map(max, board))# ✅ 2차원 리스트에서 최댓값 구하기
start, end = None, None
for i in range(N):
    for j in range(N):
        if board[i][j] == mn:
            start = (i, j)
        if board[i][j] == mx:
            end = (i, j)

cnt = 0
visited[start[0]][start[1]] = 1
DFS(start[0], start[1])
print(cnt)

• 정답!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기