N x M의 2차원 정수배열이 주어지면 인접하지 않은 위치로 k만큼 골라서 합이 가장 큰 값을 구하는 완전탐색 문제입니다.
- n, m, k
- arr
- 만약 k가 1이면 그리드에서 가장 큰 값이 최대 합이므로 Math.max 함수를 사용해서 전체 그리드 중 가장 큰 값을 반환합니다.
- 그렇지 않은 경우 dfs를 통해 인접하지 않은 위치로 k개를 선택하여 최대 합을 찾습니다.
- dfs 재귀함수를 호출합니다.
- 시작 위치와 시작위치에서 좌우상하로 1칸씩 이동해서 방문했는지를 visited 배열을 통해 체크합니다.
- tmp 배열에 선택한 숫자를 저장하고 조합의 길이가 k에 도달하면 최대값을 갱신합니다.
- 시작 위치의 탐색이 끝나면 방문 여부를 초기화하고 재귀 호출전에 선택한 숫자를 다시 제거합니다.
- 최종적으로 dfs는 최대 합을 반환합니다.
- 처음에는 인접한 숫자를 선택하지 않는것을 체크하기 위해 현재 위치에서 인접한 위치에 방문표시를 하려고 해서 풀리지 않음.
- 이후 단계별로 구현
- 인접 위치 상관없이 k개를 선택
- 현재 위치를 선택하기전에 인접한 위치를 선택했는지를 체크