[코드트리/INTERMEDIATE LOW] 수들의 합 최대화하기 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• 백트래킹

시간 복잡도 : O(N! * N)

 

사용 자료구조

- 2차원 ing형 배열
- 1차원 boolean형 배열 → 열에 대한 방문 표시 배열

 

 

재귀 함수 인자 : (int row, int sum) = (현재 행, 적힌 수들의 합)

- 종료 조건 : N개를 뽑았을 때, sum과 여태까지의 최댓값 max를 비교해 더 큰 값으로 갱신한다.

- 반복문 : 현재 행에 대해 색칠할 열을 선택한다.

┕ 현재 열을 방문하지 않은 경우, 현재 열을 방문처리하고 그 다음 행에서 열을 확인하러 가고, 적힌 수들의 합에 현재 칸의 값을 더한다.

// 현재 행에 대해 색칠할 열 선택
for(int j = 0 ; j < N ; j++) {
    if(!visited[j]) {
        visited[j] = true;
        solve(row + 1, sum + map[row][j]);	// ⭐
        visited[j] = false;
    }
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] map;
    static boolean[] visited;
    static int max = Integer.MIN_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        visited = new boolean[N];
        solve(0, 0);
 
        System.out.println(max);
    }
 
    private static void solve(int row, int sum) {
        if(row == N) {
            max = Math.max(max, sum);
            return;
        }
 
        // 현재 행에 대해 색칠할 열 선택
        for(int j = 0 ; j < N ; j++) {
            if(!visited[j]) {
                visited[j] = true;
                solve(row + 1, sum + map[row][j]);
                visited[j] = false;
            }
        }
    }
}

 

 

 

---

💦 어려웠던 점

- 객체를 생성해 숫자를 N*N개 받고, 이 중 N개를 뽑으려고 했었다, > 굳이 이럴 필요 없었음

- 인자로 어떤 값을 가져가야할지 명확히 하지 못 했다. > 현재 행과 누적 합

- 방문 배열을 2차원 배열로 만들어서 반복문을 통해 해당 행과 열과 겹치는 아이가 있는지 확인하려고 했었는데 시초가 떴다.

 

 

🧐 새로 알게 된 내용

- 객체 생성할 필요 없이, boolean형 배열을 1차원으로 생성해 행에 대한 열을 선택하게 하면 된다.

재귀 함수에서 row +1 되면서 현재 행과 겹치지 않도록 만들고, visited 표시를 통해 현재 열과 안 겹치는지 확인할 수 있기 때문이다.

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

코드트리_수들의 합 최대화하기