[백준] 1101 - 카드 정리 1(Java)

문제 파악

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

어려운 점

보통 카드를 옮기는 문제는 한 개씩 옮긴다고 생각하기 마련인데, 이 문제는 1개 이상의 카드를 한 번에 옮긴다는 점이 독특했다.

규칙을 단순화하는 게 까다로웠던 것 같다!

 

---

풀이

카드를 한 번에 많이 옮길 수 있다는 점과, 조커 박스가 있다는 점을 주목해야 한다.

정리가 필요한 박스에서 최대한 많이 꺼내서 다른 정리가 필요한 박스로 옮겨주고,
최종으로는 조커 박스에 몰아넣으면 최소 이동이 된다.

여기서 정리가 필요한 박스란 다음과 같다.

• 두 가지 이상의 색깔이 섞여 있는 경우
• 한 가지 색상으로만 이루어져 있으나, 동일 색상으로 이루어진 또 다른 박스가 있을 경우
  • 만약 1 카드만을 가진 박스가 5개라면, 그 중 4개만 손봐야 한다

 

구현은 두 개의 맵을 이용했으며, 아래 과정으로 진행했다

1. 주어진 입력에서 (상자, 색상 종류), (색상 종류, 상자)를 엔트리로 가지는 맵 생성
2. 비어있지 않은 상자 개수 카운트
3. 2에서 한 종류의 색상만을 가진 박스가 1개 이상 있다면, 1개만 정리가 필요 없으므로 1을 빼 준다.
4. 조커 박스 1개를 빼 준다

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int boxCount = Integer.parseInt(line[0]);
        int colorCount = Integer.parseInt(line[1]);

        HashMap<Integer, Set<Integer>> boxMap = new HashMap<>();
        HashMap<Integer, Set<Integer>> colorMap = new HashMap<>();
        for (int r = 0; r < boxCount; r++) {
            StringTokenizer tok = new StringTokenizer(br.readLine(), " ");
            for (int c = 0; c < colorCount; c++) {
                int val = Integer.parseInt(tok.nextToken());
                if (val > 0) {
                    boxMap.computeIfAbsent(r, k -> new HashSet<>()).add(c);
                    colorMap.computeIfAbsent(c, k -> new HashSet<>()).add(r);
                }
            }
        }

        int answer = boxMap.size();

        for (Map.Entry<Integer, Set<Integer>> c : colorMap.entrySet()) {
            int oneSizeBoxCount = (int) c.getValue().stream().filter(b -> boxMap.get(b).size() == 1).count();
            if (oneSizeBoxCount >= 1) {
                answer -= 1;
            }
        }
        System.out.println(Math.max(answer - 1, 0));
    }
}