[SWEA] 1949 : 등산로 조정 - Python

문제

최대한 긴 등산로 만들기
nxn 보드, 각 칸은 지형 높이
시작점. 가장 높은 봉우리에서 시작. 등산로는 높은지형에서 낮은 지형으로
딱 한번 최대 K만큼 지형 깎을 수 있다.

내 코드

import sys
sys.stdin = open("input.txt", "rt")

# 최대한 긴 등산로 만들기
# nxn 보드, 각 칸은 지형 높이
# 시작점. 가장 높은 봉우리에서 시작. 등산로는 높은지형에서 낮은 지형으로
# 딱 한번 최대 K만큼 지형 깎을 수 있다.

dx = [-1,0,1,0]
dy = [0,1,0,-1]
def isInner(x,y):
    if 0<=x<n and 0<=y<n:
        return True
    return False
def DFS(x,y,L, drill, prev): # 이전 좌표, 현재까지의 길이, 현재 드릴을 뚫었는지, 이전높이
    global res
    global visited
    res = max(res, L) # 최댓값 매번 갱신
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if not isInner(nx,ny): # 벗어나면
            continue
        if visited[nx][ny]:
            continue
        if g[nx][ny] < prev: # 이동 가능
            visited[nx][ny] = True
            DFS(nx,ny,L+1, drill, g[nx][ny])
            visited[nx][ny] = False
        else: # 높 -> 낮이어야 하는데 낮 -> 높인 경우
            if drill == 0: # 아직 깎지 않은 경우에 시도 가능
                if g[nx][ny] - k < prev: # 현재 좌표를 깎아서 이전 좌표보다 작게 만들 수 있다면 이동 가능
                    visited[nx][ny] = True
                    DFS(nx,ny,L+1,1, prev-1) # 최대로 가기 위해서는 이전 좌표 -1로 만드는게 베스트. 또한 깎았다는 의미로 drill에 1을 줌
                    visited[nx][ny] = False

T = int(input())
for t in range(1,T+1):
    n,k = map(int, input().split())
    g = [list(map(int, input().split())) for _ in range(n)]
    MAX = 0
    for i in range(n):
        for j in range(n):
            if g[i][j] > MAX:
                MAX = g[i][j] # 최댓값 저장

    res = 0  # 가장 긴 등산로 길이
    for i in range(n):
        for j in range(n):
            if g[i][j] == MAX: # 최댓값 만나면 탐색 시작
                visited = [[False] * n for _ in range(n)]
                visited[i][j] = True # 방문처리 햇어야만!!
                DFS(i,j,1,0,g[i][j]) # 시작점 포함해서 진행.
    print(f"#{t} {res}")

풀이법

💡 풀이법

1. 최대한 깊이 가야하는 문제이기 때문에 dfs를 이용했다.

2. 가장 높은 곳부터 시작해야 한다고 했기 때문에 맵을 다 돌면서가장 높은 높이를 먼저 구한다.

3. 다시 맵을 다 돌면서 가장 높은 높이를 만나면 dfs를 실행한다.

• 이런 식으로 문제를 푸는 것이 좋을듯

4. dfs의 인수는 좌표, 지금까지의 거리, 공사를 했는지 유무가 담긴다.

5. 일반적인 dfs와는 다르게 한번 산을 최대 k만큼 깎을 수 있는 기회가 있기 때문에 다음에 갈 지대가 지금보다 높을 때랑 낮을 때로 경우를 나누어 준다.

6. dfs가 실행되면 먼저 현재 좌표를 방문 체크 해준다.

7. 다음에 갈 지대가 지금보다 낮다면 바로 갈 수 있기 때문에 거리를 1 키워주고 다음 좌표로 dfs를 다시 실행시킨다.

8. 다음에 갈 지대가 지금보다 같거나 높고, 공사를 아직 하지 않았고, 산을 깎아야하는 정도가 k보다 크지 않다면 다음 가야할 지대를 현재 지대보다 1 작게 깎아주고 역시 다음 좌표로 dfs를 실행시킨다.

(단, dfs가 끝나면 다시 깎은 지대를 원상복구 시켜줘야 함)

9. dfs 마지막에 다시 방문 체크를 풀어줘야 다음 경로에서 또 그 위치를 갈 수 있게 된다.

10. dfs를 돌면서 지금까지의 거리가 ans보다 크면 ans를 지금까리의 거리로 바꿔준다.

(ans는 가장 긴 등산로의 길이를 담을 변수이다)

코멘트

등산로의 최대 길이를 찾는 것이기 때문에 최대한 깊에 탐색하도록 DFS로 문제를 풀었어야 했다.
또한 DFS 내부적으로는 x,y(이전 좌표) 현재까지의 길이, 드릴로 뚫었는지 확인하는 변수, 이전 좌표에서의 높이를 변수로 넘겨야만 했다.
이전 좌표에서의 높이를 넘기는 이유는 결국 최대 K까지 뚫을 수 있지만 가능하다면 이전 좌표보다 -1 작게 현재 좌표의 높이를 조정하는 것이 베스트이기 때문(물론 현재 등산로 높이가 이전 등산로보다 높은 경우에만)

가장 중요했던 것은 !!! 지나는 좌표들의 방문처리였다. 해당 방문처리를 하지 않아서 헤맸는데 꼭 생각하자!! 또한 백트랙킹 시 방문처리 원상복구.