그래프탐색 BFS | BOJ 백준 9079번 동전게임 | Python


created_at : 26 March 2024 - 3 mins read time
Tags: 완전탐색 그래프탐색 비트마스킹

Table of Contents


BOJ 백준 9079번 동전게임 | Python

📌 백준 9079번 문제 바로가기

🔎 문제 설명

🩶 실버 2

- 난이도 ★★☆☆
- 그래프탐색 BFS & 비트마스킹

C언어 수업에서 동전 뒤집기 문제를 했던 기억이 나서 반가웠지만, 예상 외로 생각해야할 것이 꽤나 많았던 문제.

뒤집을 수 있는 모든 경우의 수를 how 에 넣어놓고 하나씩 돌려주었다. 0과 1로만 구성된 9자리의 수가 나오면, 이를 2진수라고 생각하고 10진수로 다시 바꿔주어서 해당 index의 방문 여부를 고려해주어 불필요한 계산을 줄였다.

✅ 10진수가 0 이거나 511 이면 반복문 종료!



💻 내 코드

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())

def game(coins: str):
    visited = [0 for _ in range(512)]
    how = [(0,1,2),(3,4,5),(6,7,8),
           (0,3,6),(1,4,7),(2,5,8),
           (0,4,8),(2,4,6)]
    # 2진수 -> 10진수
    queue = deque([(int(coins, 2), 0)])
    visited[int(coins, 2)]=1

    while queue:
        coin, cnt = queue.popleft()
        if coin == 0 or coin == 511:
            return cnt
        for h in how:
            new = flip(list(bin(coin)[2:].zfill(9)), h)
            idx = int(new, 2)
            if not visited[idx]:
                visited[idx] = 1
                queue.append((idx, cnt + 1))
    return -1

def flip(coin, how):
    for h in how:
        coin[h] = '1' if coin[h] == '0' else '0'
    return ''.join(coin)

for t in range(T):
    tmp = []
    for i in range(3):
        c = input().split()
        tmp.append(''.join(['1' if ht=='H' else '0' for ht in c]))

    print(game(''.join(tmp)))




 

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).