[모의 SW 역량테스트, Python] 1949. 등산로 조성

접근

- NxN 개의 시작점을 전부 방문하여 가장 높은 곳을 찾습니다.

- 높은 곳은 여러개일 수 있으며 각 출발점에서 좌우상하로 가는 경우를 계산하고 기록합니다.

> 위의 정보를 바탕으로 풀이방법을 유추해 봅니다.

> DFS 입니다.

※ DFS인지 유추가 안된다. 시간이 없을 경우 DFS 문제 검색 후 10개만 한번 지문을 읽어보세요.

조건

- 조건이 있는지 확인합니다.

> 높은 곳에서 낮은 곳으로 나아갑니다.

> 공사 가능한 깊이 K에 대한 처리를 해줍니다.

DFS 로직

재귀함수 : dfs

def DFS():
    for ~ :
    	DFS()

상하좌우 : 방향좌표 변수들을 미리 지정한다.

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

방문배열 : 방문했는지 안했는지를 체크하는 배열

visited = [[0]*N for _ in range(N)]

추가 로직

최고봉 찾기

mxh = 0
    for i in range(N):
        for j in range(N):
            if mxh < mountain[i][j]: # 최고값 찾고
                mxh = m[i][j] 
ans = 0
for i in range(N):
    for j in range(N):
        if mountain[i][j] == mxh: # 최고값에서 DFS 시작
                    # start DFS

공사 여부

if(arr[ny][nx] < arr[y][x]): #공사 안해도 이동한 좌표가 전 좌표보다 작을때 
    DFS()
elif(arr[ny][nx]-k < arr[y][x]): #공사해서 이동한 좌표가 전 좌표보다 작을때 
    # 깍고
    DFS()
    # 원복

 

※ 가끔 코드 중 print(~)가 있습니다. 정리 못한 점 죄송합니다.

※ 반례가 있으면 알려주시면 감사하겠습니다.