[코드트리] 수들 중 최솟값 최대화하기 C++

문제

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

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

 

계획세우기

한 줄(row)에 하나의 수만 선택해야 하며, 행과 열이 겹치면 안 됨(중복 불가능)

visited 배열로 중복된 수가 들어가지 않게 해주기

어떤 열을 선택할지 저장하는 벡터를 선언(col_idx)

n이 3이라면 벡터에는 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}. {3, 2, 1} 이렇게 들어가게 된다.

각각에 대해 arr[row][col_idx[i]]를 해주면 행과 열이 겹치지 않게 검사할 수 있다.

풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, answer;
int arr[11][11];
bool visited[11]={false, };
vector<int> col_idx;

int FindMinNum(){
    int minNum=10000;
    for(int row=0; row<n; ++row){
        minNum=min(minNum, arr[row][col_idx[i]]);
    }
    return minNum;
}

void Choose(int curr){
    // 종료 조건
    if(curr==n){
        answer=max(answer, FindMinNum());
        return;
    }

    // 재귀 호출
    for(int i=0; i<n; i++){
        if(visited[i]) continue;

        col_idx.push_back(i);
        visited[i]=true;
        Choose(curr+1);
        col_idx.pop_back();
        visited[i]=false;
    }
}

int main() {
    // input
    cin >> n;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            cin >> arr[i][j];
        }
    }

    Choose(0);
    
    cout << answer <<'\n';
    return 0;
}