[백준] 1285번 : 동전 뒤집기

1285번: 동전 뒤집기

1285번: 동전 뒤집기

📄 문제개요

• 동전의 테이블이 주어졌을때, 행과 열을 선택하여 동전을 뒤집어서 뒷면이 가장 적게 나오는 개수를 구하는 문제이다.

🤔 문제분석

• 해당 문제는 완전탐색 + 비트마스킹으로 문제를 해결해야한다.
• 초기 접근 : 모든행을 뒤집어 보는경우와, 모든열을 뒤집어보는 경우중에서 뒷면이 더 작게 나오는 개수를 카운팅하여 출력한다.
• 위의 접근으로는 모든 경우를 탐색하지 못함으로, 문제를 해결 할 수 없다.
• 모든 행에대하여, 뒤집는경우와 뒤집지 않는 경우를 생각한다.
• 행의 개수는 N개 이고, 경우의 수는 2가지 임으로, 모든 경우의 수는 O($2^N$) 이다.
• 해당 경우의 수를 모두 탐색해보면서, T의 개수가 가장 적은 경우를 카운팅하여 답을 구한다.

📝 의사코드

1. 배열을 기존의 배열의 깊은 복사하여 새로 만든다.
2. 새로 만든 배열을 뒤집은 경우로 생각하여 H → T 로 T → H 로 바꾼다.
3. 해당 행에서 뒤집은경우와 뒤집지 않는 경우를 탐색하기위하여 1<<N 만큼 순회한다.
4. 해당 이터레이션에서 & 연산을 하여 True 인경우는 뒤집은 경우라고 생각한다.
5. 해당 이터레이션에서 & 연산을 하여 False 인경우는 뒤집지 않는 경우라고 생각한다.
6. 조합한 테이블에서 T의 개수를 샌다.
   1. 여기서 중요한건, 행마다 개수를 새는데, 뒤집은경우, 뒤집지 않은경우를 모두 따져야한다.
   2. 따라서 t_cnt += min(cnt, N-cnt) 가 도출된다.
7. 이터레이션이 끝날때까지 결과값을 계속 최소값으로 갱신해 나아간다.
8. 결과를 출력한다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
graph = [list(input().strip()) for _ in range(N)]

# 동전을 뒤집을 수 있는경우의수는 행의 기준으로 2^n 이다.
# 해당행을 뒤집은경우, 뒤집지 않은경우가 2가지이고, 행의 개수가 n개 이니까 2^n이다.
rev_graph = [ graph[i][:] for i in range(N)]

for i in range(N):
    for j in range(N):
        if rev_graph[i][j] == 'T':
            rev_graph[i][j] = 'H'
        else:
            rev_graph[i][j] = 'T'
            
ans = N**2 + 1
for b in range(1 << N): # 비트마스킹
    temp = []
    for i in range(N):
        if b & (1 << i): # 뒤집은경우
            temp.append(rev_graph[i][:])
        else:
            temp.append(graph[i][:])
    
    t_cnt = 0
    for i in range(N):
        cnt = 0
        for j in range(N):
            if temp[j][i] == 'T':
                cnt += 1
                
        t_cnt += min(cnt, N-cnt)
        
    ans = min(t_cnt, ans)
    
print(ans)

🎯 피드백 및 개선사항

• 초기 생각했던 코드는 모든 경우의 수를 탐색하지 못하고, 문제를 해결 할 수 없다.
• 그 다음에 생각했던건 DFS로 접근하여, 모든경우의수를 탐색한다, 1번행을 뒤집는경우, 뒤집지않는경우를 탐색해 나아간다.
• 추후에 문제를 풀어볼때 DFS로 접근하여 문제를 풀어볼 것이다.

❓다른사람은 어떻게 풀었을까?

• 해당문제는 거의 모든사람이 비트마스킹으로 문제를 해결 하였습니다.