등산로 조성 [SWEA 모의 SW 역량 테스트]

// 1시간 반 소요

 

1. 문제 접근 방법

- SWEA에서 문제를 풀 때, 전체 다 지우고, 내가 사용할 것들을 넣으면 된다

-> 또한, for 문 같은 경우는 있는 그대로 사용하려면, 그 양식에 맞게 사용해야 한다

 

- 문제를 DFS로 접근했다

-> DFS로 접근할 때, 테스트 케이스를 잘 고려해야 한다

-> 특히, 중요한 것이 최대 K만큼 팔 수 있다는 것을 어떻게 반영할지이다.

-> 최대 K만큼 팔 수 있고, K-1, K-2... 도 팔 수 있으나, 

    최소한, 현재 칸보다는 하나 작게 만들때까지는 파야 한다. 

    왜냐면 팠는데, 현재 칸과 같거나 현재 칸보다 높다면, 이동이 불가능하기 때문이다. 

    이 점을 잘 고려해야 한다

 

- if K>=gap이라는 조건도 중요하다.

  왜냐하면 이 조건이 있어야만, 다음 방문할 곳을, 현재 점보다 높이가 1이라도 낮게 만들 수 있음을

  알 수 있는 것이기 때문이다. 

 

- 또한, pave로 팠는지 안 팠는지 판단했는데, 한 번 True가 되면, 그 이후는 계속해서 True가 되도록 해야 한다. 

 

- DFS로 접근했는데, BFS로 접근하는 방법도 있는지 생각해볼 필요가 있다. 

 

- path는 디버깅 용도로 사용했고, 실제 답을 구하는데 필요한 것은 아니다. 

 

- 또한 maxLen과 totalMaxLen을 잘 구분해주는 것도 중요하다. 

 

 

2. 코드 

import copy 

T = int(input())
maxLen = 0 
totalMaxLen = 0 

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

def dfs(x, y, N, K, board, len, visited, pave, path):
    
    global maxLen
    
    maxLen = max(maxLen, len)
    
    curr = board[x][y]
    
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0<=nx and nx<N and 0<=ny and ny<N and visited[nx][ny] == False:
            
            if curr > board[nx][ny]:
                visited[nx][ny] = True
                path.append([nx, ny, board[nx][ny]])
                dfs(nx, ny, N, K, board, len+1, visited, pave, path)
                path.pop()
                visited[nx][ny] = False
                
            elif curr <= board[nx][ny] and pave == False:
                target = curr-1
                gap = board[nx][ny]-target
                origin = board[nx][ny]
                if K>=gap:
                    for j in range(K, gap-1, -1):
                        board[nx][ny] -= j
                        visited[nx][ny] = True
                        path.append([nx, ny, board[nx][ny]])
                        dfs(nx, ny, N, K, board, len+1, visited, True, path)
                        path.pop()
                        board[nx][ny] = origin 
                        visited[nx][ny] = False 
                    
                    
                
                
                
                
            
    
    


for i in range(T):
    
    totalMaxLen = 0 
    N, K = map(int, input().split())
    
    board = [] 
    
    for j in range(N):
        row = list(map(int, input().split()))
        board.append(row)
        
        
    arr = [] 
    maxHeight = 0 
    
    for j in range(N):
        for k in range(N):
            if board[j][k] > maxHeight: 
                maxHeight = board[j][k] 
                
    
    for j in range(N):
        for k in range(N):
            if board[j][k] == maxHeight:
                arr.append((j, k))
    
    
    for x,y in arr:
        
        tmpBoard = copy.deepcopy(board)
        maxLen = 0 
        visited = [[False]*N for _ in range(N)]
        
        visited[x][y] = True 
        pave = False
        path = []
        path.append([x,y, tmpBoard[x][y]])
        dfs(x, y, N, K, tmpBoard, 1, visited, pave, path)
        totalMaxLen = max(totalMaxLen, maxLen)
    
    print("#" + str(i)+" " + str(totalMaxLen))