[백준-파이썬] 23085: 판치기

문제로 가기!

처음에는 어떻게 풀지 감도 잡히지 않았다. 문제 분류가 BFS라는데,, 이게 왜 BFS인지...
뭔가 수학적인 개념이나 그리디로 접근해야 하는 거 아닌가..? 하는 생각도 들었다.
그러다 스터디에서 다른 분의 설명을 듣고 나서 풀었다!

BFS로 풀었다.

매번 K개 뒤집기를 해야 하는데, 이때 뒷면으로 뒤집어진 동전을 0~K개를 뒤집었을 때 어떻게 되는지 본다.
만약에 지금 뒷면인 동전이 5개인데, 7개 뒤집는 것은 말이 안되니까 그런 경우는 제외하고!

가능한 경우를 봤을 때, N개 동전 모두 뒷면이라면 그때까지 K-뒤집기를 한 횟수를 리턴하면 된다.
그게 아니라면, deque에 그 상태에서 뒷면인 동전 개수와 그때까지 뒤집기 횟수를 넣어주었다.
visited 체크를 한 후에 deque에 넣는데, 이때 체크의 대상은 바로 동전 뒷면의 개수이다 !

import collections
import sys

input = sys.stdin.readline


def bfs(back_cnt):
    visited = [0] * (N + 1)  # 뒤집힌 동전이 몇 개인지

    q = collections.deque()
    visited[back_cnt] = 1
    q.append((back_cnt, 0))  # 뒤집힌 동전의 개수, 몇 번 K-뒤집기 사용했는지

    while q:
        tmp_back_cnt, k_turn_cnt = q.popleft()
        tmp_front_cnt = N - tmp_back_cnt
        for i in range(K + 1):  # 0~K개의 뒷면인 동전 뒤집기
            turn_back = i  # 뒷면인 동전 뒤집을 개수
            turn_front = K - i  # 앞면인 동전 뒤집을 개수

            if turn_back > tmp_back_cnt or turn_front > tmp_front_cnt :  # 뒤집힐 수 있는 개수보다 뒤집을 개수가 클 수는 없음
                continue

            back_cnt = tmp_back_cnt - turn_back + turn_front

            if back_cnt == N:
                return k_turn_cnt + 1

            if visited[back_cnt]:  # 이미 이 동전 개수일 때 K-뒤집기한 적이 있으면 더 이상 하지 않기
                continue
            visited[back_cnt] = 1
            q.append((back_cnt, k_turn_cnt + 1))

    return -1

N, K = map(int, input().strip().split())
S = input()

back_cnt = 0
# 초기 상태 세팅
for i in range(N):
    if S[i] == 'T':
        back_cnt += 1

if back_cnt == N:
    print(0)
else:
    ans = bfs(back_cnt)
    print(ans)