[백준][Python]1285번(동전 뒤집기)

뱌·2023년 11월 2일

백준 문제풀이

목록 보기

153/159

백준 1285번

✔️ 문제 풀이

각 행에 대해 조합을 생성해서 문제를 풀려고 생각했지만 시간초과가 나지 않을까? 라는 생각이들어 시도하지 않고 다른 사람의 풀이를 참고했다.
그런데 결국 행을 뒤집는 논리는 동일하기에 실행시간은 큰 차이가 없다.
이 문제는 비트마스킹을 활용하면 더 편리하게 구현할 수 있지만 combinations 메소드를 활용해서도 구현할 수 있다.

◾ 그리디 알고리즘

이 문제는 행과 열을 모두 뒤집어야하는데 행을 먼저 뒤집는다고 가정했을 때, 행을 뒤집는 시점에는 그 행을 뒤집는게 맞는 것인지 아닌지 판단할 수 없다.
따라서 각각의 행을 뒤집거나 뒤집지 않는 모든 경우의 수를 고려해서 문제를 풀어야한다.
행 뒤집기에서 모든 생성된 케이스에 대해서 열을 뒤집을지 말지를 고려해줘야한다.
열을 뒤집을 때는 해당 열을 뒤집는 것이 맞는지 아닌지 판단 가능하다.

✔️ 비트마스킹

◾ 행 뒤집기

행이 3개라면 행의 뒤집기에서는 총 2X2X2개의 경우의 수를 고려해줘야 한다.
⇒ 1) for case in range(2**N)
원본 배열은 변해서는 안되기 때문에 각각의 케이스에 해당하는 배열을 생성해줘야한다.
⇒ board_temp = []
1)에서 생성된 케이스에 따라 행 뒤집기한 결과의 배열을 생성한다.
이때 해당 행을 뒤집을지 말지 판단하는 조건문이 필요하다.
만약 case가 7, 즉 111이라면 모든 행을 뒤집어야 한다. 그런데 이를 어떻게 판단할 것인가?
첫번째 행을 뒤집어야 하는지 여부를 판단하고 싶으면 비트의 첫번째 자리가 1인지 아닌지를 판단하면 된다.
따라서 1부터 시작하여 행의 개수만큼 1의 비트를 왼쪽으로 이동시키며 각 자리수가 1인지 아닌지를 확인한다.
⇒ if case & (1 << i)
ex. loop-1) i=0, 101 & 001은 참(001)이므로 0번째 행을 뒤집는다.
ex. loop-2) i=1, 101 & 010은 거짓(000)이므로 1번째 행은 뒤집지 않는다.
ex. loop-3) i=2, 101 & 100은 참(100)이므로 2번째 행을 뒤집는다.
위 조건문이 참이면 board_reversed[i]을 board_temp에 append하고, 거짓이면 board[i]를 append한다.

◾ 열 뒤집기

행 뒤집기에서 생성된 board_temp 배열을 활용하여, 열을 뒤집고 T의 개수를 센다.
열을 뒤집을 때는 뒤집을지 말지를 결정할 수 있다.
열을 기준으로 T의 개수를 세고, 뒤집을 때의 값(T의 개수)과 뒤집지 않을 때의 값(N-T의 개수)를 비교하여 작은 쪽을 total_count에 더해준다.
열 뒤집기가 끝나면 total_count을 answer값과 비교하여 더 작은 값으로 answer을 업데이트해준다.

최종 제출 코드

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(str, input().rstrip())) for _ in range(N)]

answer = N*N

# 이걸 미리 만들어두면 행 뒤집기 시 매번 리스트를 확인하고 반전시켜줄 필요가 없다
board_reversed = [["H"] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if board_reversed[i][j] == board[i][j]:
            board_reversed[i][j] = "T"

for case in range( 2**N ):
    board_temp = []
    for i in range(N):
        if case & (1 << i):
            board_temp.append(board_reversed[i])
        else:
            board_temp.append(board[i])

    total_count = 0
    for j in range(N):
        count = 0
        for i in range(N):
            if board_temp[i][j] == "T":
                count += 1
        total_count += min(count, N-count)
    answer = min(answer, total_count)

print(answer)

✔️ 조합(combinations)

기본적인 논리는 비트마스킹 활용 풀이와 공유하고 행 뒤집기 구현 방식에만 차이가 있다.
뒤집을 행의 개수를 선택하고(0~N),
⇒ for i in range(N+1)
N중에서 i개(뒤집을 행의 개수)를 골라 조합을 생성(뒤집을 행의 조합)한다.
⇒ for rows in combinations(range(N), i)
생성된 각 조합에 대해 조합 내에 존재하는 값을 행의 인덱스로 하여 값이 조합에 존재하면 뒤집어서 append하고, 존재하지 않으면 뒤집지 않은채로 append한다.

for i in range(N+1):
  for rows in combinations(range(N), i):
    board_temp = []
    for j in range(N):
      if j in rows:
        board_temp.append(board_reversed[j])
      else:
        board_temp.append(board[j])