[코드트리/INTERMEDAITE LOW] 수들 중 최솟값 최대화하기 (JAVA)

🔺 문제

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

 

🧩  해결 아이디어

• 백트래킹 (조합)

. 필요 자료구조

┕  격자 저장할 2차원 int형 배열

┕  중복 방지용 boolean형 배열

┕  조합 숫자들 저장용 int형 리스트 (열 저장)

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

 

- 2차원 배열에 값을 입력받는다.

- 1부터 N행까지 돌며 어떤 열을 색칠할지 N개의 값을 뽑아 조합을 생성한다.

- 해당 조합에 있는 숫자들 중 최솟값을 구하고, 이 최솟값을 현재 최댓값과 비교해 갱신한다.

 

 

💥 유의사항

각 행과 열에 1개의 색칠된 칸만 오게 한다고 하였으므로, 중복없이 뽑아야 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, answer;
 
    static int[][] grid;
    static boolean[] visited;   // 중복 방지용 배열
 
    static List<Integer> list = new ArrayList<>();  // 조합 저장용 리스트 (열 저장)
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        grid = new int[N][N];
 
        int idx = 0;
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
  
        visited = new boolean[N];
        backtracking(0);
        System.out.println(answer);        
    }
 
    // 각 열의 위치에 대한 순열 생성
    private static void backtracking(int row) {
        // N개 뽑았으면, 조합에 있는 숫자들 중 최솟값을 구하고, 이 값을 최댓값과 비교해 갱신
        if(row == N) {
            answer = Math.max(answer, getMin());
            return;
        }
 
        for(int i = 0 ; i < grid.length ; i++) { // 현재 행에 색칠할 열 선택
            if(visited[i])  continue;
 
            visited[i] = true;
            list.add(i);
 
           backtracking(row + 1);
 
            visited[i] = false;
            list.remove(list.size() - 1);
        }
    }
 
    // 색칠된 칸에 적힌 수들 중 최솟값 구하기
    private static int getMin() {
        int min = Integer.MAX_VALUE;
 
        for(int i = 0 ; i < list.size() ; i++) {
            min = Math.min(min, grid[i][list.get(i)]);
        }
 
        return min;
    }
}

 

---

💬 느낀 점

재밌지만 쉽지 않은 백트래킹....

 

 

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

---

(참고)

코드트리

[코드트리 챌린지] 수들 중 최솟값 최대화