[SWEA] 1949. [모의 SW 역랑테스트] 등산로 조성

 

SW Expert Academy

 

일단 높은 봉우리들을 먼저 다 찾고, 그 봉우리를 기준으로 DFS 완전 탐색을 돌려주었다.

cut 여부와 cnt를 함께 넘겨주며 옆으로 갈 수 있고, cut 한 적이 없으면 최대 cut할 수 있는 만큼 돌려보며 cut 해준다.

max_climb(가장 긴 등산로) 를 어떻게 갱신 해줄지 고민했는데 그냥 solve 함수를 호출할 때마다 갱신하는 걸로 했다.

solve 안의 if-else 문을 작성할 때 not cut 해준 걸 깜빡하고 그냥 else 로 돌렸다가 답이 안 나와서 뭐가 잘못된 건지 한참 생각했다..(-_-)

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


def solve(y, x, cnt, cut):
    global max_climb
    max_climb = max(cnt, max_climb)

    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx]:
            # 옆에 있는 애가 큼 + 한 번도 cut 안 한 상태
            if maps[y][x] <= maps[ny][nx] and not cut:
                for c in range(1, k+1): # 모든 cut 다 해 봄
                    maps[ny][nx] -= c
                    if maps[ny][nx] < maps[y][x]:
                        visited[ny][nx] = 1
                        solve(ny, nx, cnt+1, True)
                        visited[ny][nx] = 0
                    maps[ny][nx] += c
            # 옆에 있는 애가 작음, cut 상태 그대로 넘겨줌
            elif maps[y][x] > maps[ny][nx]:
                visited[ny][nx] = 1
                solve(ny, nx, cnt+1, cut)
                visited[ny][nx] = 0


for tc in range(1, int(input())+1):
    n, k = map(int, input().split())
    maps = []
    high_mountains = []
    high_mountain = 0
    max_climb = 0
    for _ in range(n):
        maps.append(list(map(int, input().split())))

    # 높은 봉우리 저장
    for i in range(n):
        for j in range(n):
            if maps[i][j] > high_mountain :
                high_mountains = [(i, j)]
                high_mountain = maps[i][j]
            elif maps[i][j] == high_mountain :
                high_mountains.append((i, j))

    # 높은 봉우리부터 완전 탐색
    for i, j in high_mountains:
        visited = [[0]*n for _ in range(n)]
        visited[i][j] = 1
        solve(i, j, 1, False)

    print('#{} {}'.format(tc, max_climb))