[BOJ] 1101번 - 카드 정리1

문제 링크

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

문제 유형

Greedy

🌈문제

태수는 카드 수집가이다. 태수는 카드를 박스에 넣어서 보관한다. 어느날, 태수의 동생이 태수의 카드를 가지고 놀았고, 박스에 다시 넣어두었다. 하지만, 태수가 넣는 기준을 지켜서 넣은 것이 아니기 때문에, 태수는 카드를 다시 정리하려고 한다.
박스는 N개가 있고, 카드는 색상으로 구분할 수 있다. 서로 다른 색상의 수는 M개가 있다. 태수는 아래 조건을 지키게 하기 위해 카드를 정리하려고 한다.

1. 박스 최대 1개는 조커 박스로 지정할 수 있다. 조커 박스는 색이 다른 카드를 보관해도 된다.
2. 조커 박스를 제외한 모든 박스는 비어있거나, 같은 색의 카드만 보관해야 한다.
3. 같은 색을 가진 모든 카드는 모두 같은 박스에 있어야 한다. 이때 조커 박스에 들어있는 카드는 제외한다. 같은 색을 가진 모든 카드가 조커 박스에 들어있는 것도 가능하다.

각각의 박스에 각 색상을 가진 카드가 몇 장 들어있는지 입력으로 주어진다. 이때 최소 몇 번 이동해서 위의 조건을 지키게 할 수 있는지 구해보자. 이동 한 번은 한 박스에서 1장 이상의 카드를 빼 다른 박스에 넣는 것을 의미하며, 빼낸 카드의 색상은 같지 않아도 된다.

입력

첫째 줄에 박스의 개수 N과 카드 색상의 개수 M이 주어진다. 둘째 줄부터 N개의 줄에 한 박스에 들어있는 카드의 정보가 주어진다. 카드의 정보는 M개의 정수로 이루어져 있고, 첫 정수부터 1번 색상 카드의 수, 2번 색상 카드의 수, ..., M번 색상 카드의 수이다.

출력

첫째 줄에 문제의 조건을 지키게 하기 위한 최소 이동 횟수를 구해보자

1. 첫 시도 + 아이디어

• 각 행을 조사하였을 때, 0이 아닌 숫자가 가장 많은 행이 조커박스라고 가정
  - 여기서 첫 생각이 잘못됨. 항상 0이 아닌 숫자가 가장 많다고 하여 조커박스라고 가정하는 것은 잘못된 것이다. 그래서 for문을 이용하여 모든 행을 조사할 수 있도록 변경하여야!
• 행을 조사하였을 때, 0이 아닌 숫자가 2개 이상 나오면 조커박스에 모두 넣는다. (횟수는 1로 생각)
• 위의 과정에서 걸러진 행 제외하고, 같은 열에 같은 색을 가진 카드가 여러 장이 있다면 그 카드를 옮기는 것에 대한 수도 고려한다.

아래는 이에 따른 생각에 이어 작성한 코드이다.
결국 시간초과가 나온다. (for문이 여러번 중첩되어 최소 O(50^3)의 복잡도가 발생. 시간복잡도 충족X

import sys
import copy
input=sys.stdin.readline
n,m=map(int, input().split())
boxlist=[0 for _ in range(n)]
boxlist2=[0 for _ in range(n)]

for i in range(n):
    boxlist[i]=list(map(int, input().split()))
for i in range(n):
    for j in range(m):
        boxlist[i][j] = boxlist2[i][j]
finallist=[]
for k in range(n):
    boxlist[k] = [0 for _ in range(m)]
    finalcount = 0
    tmpcount = 0
    for i in range(n):
        for j in range(m):
            if boxlist[i][j] > 0:
                tmpcount = tmpcount + 1
        if tmpcount >= 2:
            boxlist[i]=[0 for _ in range(m)]
            finalcount = finalcount + 1
        tmpcount = 0
    countlist=[]
    count=0
    for j in range(m):
        for i in range(n):
            if boxlist[i][j] >0 :
                count = count + 1
                if count >=2:
                    finalcount = finalcount + (count-1)
        count=0
    boxlist = copy.deepcopy(boxlist2) 
    finallist.append(finalcount)
print(min(finallist))

결국 처음에 생각하였던 아이디어는 시간초과가 발생하기 때문에 또다른 방법으로 접근해보았다.

2. 2차원 배열을 건들지 말고 다른 장치를 만들어 보자.

문제를 항상 만족할 수 있는 조건은
조커 행으로 모든 행에 있는 카드들을 옮긴다입니다. 답이 n-1 이하가 되기 위해서는
1. 기존에 모든 행이 0인 행이 있어야 한다. (카드가 없는 빈 상자만 있다.)
2. 기존에 상자 안에 카드가 하나만 존재한다.
단 이럴 경우 주의!!
4 2
0 1
0 2
0 2
0 3

이럴 경우에는 어떻게 옮겨야 할까? 딱 한번만 옮기면 되겠지.. 1번 옮긴다.(하나만 세주면 됨)

즉 Brute Force로 조커박스가 될 수 있는 모든 경우를 확인해 보면서 해당 조건을 만족하는 최소값을 구해주자. 그리고 기존의 2차원 배열을 건들지 말고 검사할 수 있는 방법을 생각해보자.
기존에 시간초과가 났기 때문에...

import sys
input=sys.stdin.readline
n,m=map(int, input().split())
boxlist=[0 for _ in range(n)]
rowcheck=[0 for _ in range(50)]
visitcheck=[0 for _ in range(50)]

for i in range(n):
    boxlist[i]=list(map(int, input().split()))

for i in range(n):
    for j in range(m):
        if(boxlist[i][j]) :
            rowcheck[i]= rowcheck[i] + 1 # 각 행에 0이 아닌 것이 몇 개 있는지 체크

finalresult=[]
for k in range(n):
    finalcount = 0
    for i in range(n):
        if(i==k):
            continue
        elif (rowcheck[i]>1):
            finalcount = finalcount + 1
        elif (rowcheck[i]==0):
            continue
        else:
            checkpoint= False
            for j in range(m):
                if(boxlist[i][j] and (not visitcheck[j])):
                    visitcheck[j]=1
                    checkpoint = not checkpoint
                    break
            if (not checkpoint) :
                finalcount = finalcount +1
    finalresult.append(finalcount)

print(min(finalresult))

0인 행은 모두 건너뛴다고 생각한다. 그리고 else문을 통해 각 행에 1개만 들어 있는 카드에 대한 고려를 완료한는 것이다. 조커박스라고 생각한 부분은 건너뛰어야 한다.

진짜진짜 오랜만에 BOJ 풀었느데 골3문제로 시작하다 보니까 머리 터질 뻔했따. ... PS 열심히 합시다