[SWEA 1949] 등산로 - DFS, 파이썬

 

 

 

DFS 문제가 점차 익숙해지나 했더니  조금의 심화가 나오면 헤매게 된다.

 

아직 배운지 얼마 안됐고, 요새 장고를 배우느라.. 바빠져서 알고리즘 문제를 풀지 못하고 있다ㅠ

 

 

조급해하지 않기...ㅎㅎ 1일 1알을 목표로..!! 

 

 

 

 

 

이전에 풀었던 DFS의 문제는 좌표 한개로부터 다른 좌표로 가는 거라 고려해야할 사항이 많지 않았다.

 

그런데 등산로 문제는

 

일단 시작하는 좌표가 여러개이고 언제끝날지 모른다.

 

그래서 끝나는 지점에서 1) 몇번 왔는지 체크해줘야 하며, 

 

또한, 등산로를 한번 허용하는 길이만큼 줄일 때 줄인 것을 반영하되, 다른 등산로들에게는 영향을 주지 않아야 한다.

 

그래서 등산로 길이를 줄여야하는 상황에서는 등산로 길이를 줄인다음 temp 변수를 사용해 원상복구 시켜주었다.

 

 

 

 

 

처음에 deepcopy를 사용했으나, 시간이 많이 걸려 후에 visited를 그냥 바꿔주는 식으로 진행했다.

 

다른 코드를 보니 아예 visited 했던 좌표들을 리스트에 넣고 빼면서 확인하는 방식도 있었다.

 

 

 

 

delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def DFS(r, c, cnt, K_used):
    global max_length
    visited[r][c] = 1
    for dt in range(4):
        nr = r + delta[dt][0]
        nc = c + delta[dt][1]
        if 0 > nr or nr >= N or 0 > nc or nc >= N or visited[nr][nc] == 1: continue
        # 이전 등산로보다 낮을 경우
        if map_info[nr][nc] < map_info[r][c]:
            visited[nr][nc] = 1
            DFS(nr, nc, cnt + 1, K_used)
            visited[nr][nc] = 0
        # 허용 깊이까지 깎을 수 있고, 아직 깎아본적 없을때
        elif map_info[nr][nc] - K < map_info[r][c] and K_used == 0:
            temp = map_info[nr][nc]
            map_info[nr][nc] = map_info[r][c] - 1
            K_used = 1
            visited[nr][nc] = 1
            DFS(nr, nc, cnt + 1, K_used)
            K_used = 0
            visited[nr][nc] = 0
            map_info[nr][nc] = temp
    else:
        if max_length < cnt:
            max_length = cnt

T = int(input())
for tc in range(1, T+1):
    N, K = map(int, input().split())
    map_info = []
    for i in range(N):
        map_info.append(list(map(int, input().split())))


    # 가장 높은 봉우리 찾고 좌표 저장
    start = []
    max_peak = 0
    for i in range(N):
        for j in range(N):
            if map_info[i][j] < max_peak: continue
            if map_info[i][j] > max_peak:
                start = []
            max_peak = map_info[i][j]
            start.append((i, j))

    max_length = 0
    for i in range(len(start)):
        sr, sc = start[i][0], start[i][1]
        visited = [[0] * N for _ in range(N)]
        DFS(sr, sc, 1, 0)
    print(f'#{tc} {max_length}')