[백준] 카드 정리 1 1101번 (c++) 구현

출처 : https://www.acmicpc.net/problem/1101

 

풀이 방법

 

문제에서 핵심 포인트는 한 상자에서 다른 상자로 카드를 옮길 때 색상에 상관없이 한 번에 옮길 수 있다는 점이다.

이를 통해 만약 비어있는 상자가 아니거나 하나의 색상 카드만 존재하지 않는 경우라면 모든 카드를 조커 상자로 옮기면 된다.

또한 핵심 포인트 때문에 카드의 색상이 가장 다양하게 존재하는 상자가 무조건 적 조커가 되지 않으므로 모든 상자를 돌아가며 조커가 될 때 가장 작은 횟수를 구하면 된다.

 

만약 1개의 색상만 존재하는 상자가 이미 앞 전에 같은 색상만 존재하는 상자가 있다면 옮겨 주어야 하므로 이 부분만 유의하면 된다.

 

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>

using namespace std;

//하나나 비어 있는거만 하고 나머지는 다 옮기기 즉 다 비우기
int visited[51];
int N, M; //박스의 수, 카드의 색상 수
vector<vector<int> > box;

int main() {
    cin >> N >> M;
    memset(visited, 0, sizeof(visited));

    box.resize(N);
    int rownum[N];

    for (int i = 0;i < N;i++) {
        int cnt = 0;
        for (int j = 0;j < M;j++) {
            int a;
            cin >> a;
            if (a > 0) {
                cnt++;
            }
            box[i].push_back(a);
        }
        rownum[i] = cnt; // row의 개수 저장하기
    }

    int ans = 987654321;

    for (int i = 0;i < N;i++) { //박스를 돌아가며 조커를 선택한다. i번째 박스가 조커이다.
        int total_cnt = 0;
        memset(visited, 0, sizeof(visited)); // 방문 배열 초기화
        for (int j = 0;j < N;j++) {
            if (i == j) continue; // 조커인 경우

            if (rownum[j] == 0) { // 비어 있는 경우
                continue;
            }
            
            if (rownum[j] > 1) { // 한 가지 이상의 색이 존재하는 경우
                total_cnt++;
            } 

            if (rownum[j] == 1) { // 하나만 있는 경우
                for (int k = 0;k < M;k++){
                    if (box[j][k] != 0) { // 존재하는 색의 인덱스
                        if (visited[k] == 0) visited[k] = 1; // 선택되지 않은 경우
                        else total_cnt++; // 이미 선택되어서 옮겨야 함
                    }
                }
            }

        }
        ans = min(ans, total_cnt);
    }

    cout << ans;
    return 0;
}