[BOJ][Python] 백준 23085 번: 판치기

1일 1PS 67일차!

📚 문제

---

골드 3 판치기

💡 풀이 과정

---

• 흔한 DFS 문제이다.
• visited 설정 후 가장 짧은 경로를 출력한다.
• 처음에는 실제로 동전을 뒤집었지만 HHHHH 에서 TTHHH 와 HHTTT 의 차이가 전혀 없었다.
  • 둘을 하나의 데이터로 만들자면 H 와 T 의 갯수로 파악할 수 있다.

📌포인트

---

• HHHHH 일 때는 T 를 뒤집을 수가 없다.
  • 이를 위한 if K - i > h or i > t 조건문이 있다.
  • 부등식을 풀어 visited 조건문과 하나로 만들어낼 수 있다.

💻 코드

---

from collections import deque

N, K = map(int, input().split())
coins = input()
visited = set()

state = (coins.count('H'), coins.count('T'), 0)


def bfs():
    queue = deque()
    queue.append(state)

    while queue:
        h, t, c = queue.popleft()
        if h == 0:
            return c
        for i in range(K + 1):
            if K - i  > h or i > t:
                continue

            nh = h - (K - 2 * i)
            nt = t + (K - 2 * i)
            if nh < 0 or nt < 0 or (nh, nt) in visited:
                continue

            visited.add((nh, nt))
            queue.append((nh, nt, c + 1))

    return -1


print(bfs())