[백준]1034 램프 #수학#union find

1. 풀이

처음엔 dfs로 완전탐색했고 시간초과가 발생했다. (소스코드1)

규칙을 찾아서 풀어야 한다. 처음에 같은모양을 갖고 있지 않는 행은 열 단위로 스위치를 누를 때 절대 같아질 수 없다. 즉

(1) 동시에 켜져있는 행이 될 수 있는 행들 <=> 시작할 때 같은 모양을 갖는 행들 (union find로 찾았다)

(2) 해당 집합이(같은 모양을 갖는 행들) k번째에 켜져있는상태가 될 수 있는가? <=> 시작할때 0의 개수와 k를 2로 나눈 나머지가 같다

​

2. 소스코드1 (시간초과,dfs 완전탐색)

N,M=map(int,input().split())
L=[]
for i in range(N):
    L.append(list(input()))
k=int(input())

def push(j):
    for i in range(N):
        if L[i][j]=="0":
            L[i][j]="1"
        else:
            L[i][j]="0"

def countRow():
    cnt=0
    for i in range(N):
        isOn=True
        for j in range(M):
            if L[i][j]=="0":
                isOn=False
                break
        if isOn:
            cnt+=1
    return cnt

#num번 누름
def dfs(num):
    global ans
    if num==k:
        nowCount=countRow()
        if ans<nowCount:
            ans=nowCount
        return

    for j in range(M):
        push(j)
        dfs(num+1)
        push(j)

ans=0
dfs(0)
print(ans)

 

3.소스코드2 (통과)

import sys
N,M=map(int,input().split())
L=[]
for i in range(N):
    L.append(list(input()))
k=int(input())
parent=[i for i in range(N)]

def find(a):
    if a==parent[a]:
        return a
    else:
        parent[a]=find(parent[a])
        return parent[a]
#a에 b를 붙이기
def union(a,b):
    a=find(a)
    b=find(b)
    parent[b]=a

for i in range(N):
    for j in range(i+1,N):
        if L[i]==L[j]:
            union(i,j)

for i in range(N):
    find(i)
tempL=[0 for i in range(N)]
for i in range(N):
    tempL[parent[i]]+=1
cntL=[]
for i in range(N):
    cntL.append([tempL[i],i])

cntL.sort(reverse=True)
for num,rowNum in cntL:
    cntZero=0
    for j in L[rowNum]:
        if j=="0":
            cntZero+=1
    if k>=cntZero and k%2==cntZero%2:
        print(num)
        sys.exit()
print(0)