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

1주차 실력진단 결과

실력진단은 주마다 치뤄서 얼마나 성장했는지 확인하는 지표이기 때문에 이미 실력진단한 주차의 풀이글에서는 한번만 올릴 생각이다

문제

https://www.codetree.ai/missions/14/problems/maximin-of-numbers?&utm_source=clipboard&utm_medium=text

풀이방법

• 백트래킹을 사용하여 열을 어떤 순서로 뽑을 것인지 결정
• 각 행과 열에 정확히 1개의 칸을 색칠하기 위해서 중복없이 경우의 수를 뽑아야함

코드

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static int ans = 0;
    static int[][] grid; // 격자
    static boolean[] visited; // 중복을 막기 위한 방문처리 배열
    static ArrayList<Integer> list = new ArrayList<>(); // 경우의 수를 담아 놓기 위한 리스트
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        grid = new int[n][n]; // 격자 초기화
        for (int i = 0; i < n; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                grid[i][j] = Integer.parseInt(stk.nextToken());
            }
        }

        visited = new boolean[n]; // 방문배열 초기화
        backtracking(0);
        System.out.println(ans);
    }

    private static void backtracking(int count) {
        if (count == n) { // n개를 뽑았다면
            int num = Integer.MAX_VALUE;
            for (int i = 0; i < list.size(); i++) { // 각 위치의 격자값 중 최솟값을 num 변수에 저장
                num = Math.min(num, grid[i][list.get(i)]);
            }
            ans = Math.max(ans, num); // num 변수들 중 최댓값을 뽑아준다
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i]) { // 방문했으면 뽑지 않음
                continue;
            }

            visited[i] = true; // 방문처리
            list.add(i); // 수를 뽑음

            backtracking(count + 1); // count를 늘려줌

            list.remove(list.size() - 1); // n개를 뽑은 후의 과정을 거치고 뽑은 수를 지워줌
            visited[i] = false; // 방문배열도 다시 false로 처리
        }
    }
}

느낀점

백트래킹 알고리즘을 사용하는 것에 있어서 사실 굉장히 어려움을 겪고 있었다.
하지만 점점 익숙해지는 것을 몸으로 체감하고 있고 이 중에서도 격자 유형은 처음 본 것이라 익숙해지는데 시간이 좀 걸렸다.
그래도 익숙해지고 풀 수 있는 것을 체감하고 있어서 기분이 굉장히 좋고 더욱 성장할 수 있을거라 생각한다.