[Python][백준 23085][BFS] 판치기 - 컴도리돌이

반응형

23085번: 판치기

---

풀이 과정

 

해당 문제를 보고 생각난 알고리즘은 깊이 우선 탐색이 떠올랐지만,

시간 초과가 발생할 것을 우려해

한 동안 어떤 알고리즘을 해결해야 하나 어려움이 많았던 문제였다.

🥲 

 

할 수 없이 알고리즘 분류를 보고 경악에 금치 못했다.

해당 문제를 너비 우선 탐색으로 해결해야 하다니,,,

내가 그동안 어떤 고정관념에 박혀 있던 건지,,

알고리즘 분류를 보고 차근차근 고민을 하였다. 

 

우리는 주어진 N개를 모두 뒷면으로 바꿔야 한다.

그렇다면 주어진 동전의 상태에서 가져올 것은 뒷면이 몇 개 있는지만 중요하다.

문제에서 서로 다른 K개의 동전을 한 번에 뒤집을 수 있기 때문에(자리 상관없음)

현재 상황에서 앞면이 몇 개인지 뒷면이 몇 개인지만 알면 된다.

 

1. 주어진 n과 k를 입력받는다. 

 

2. 해당 문제를 BFS 문제로 해결하려고 한다.

(주어진 알고리즘 분류로 푸는 편..😂)

그러기 때문에 큐를 사용하는데,

큐에는 현재 상황의 뒷면의 개수와 게임을 한 횟수를 저장시킨다.

 

3. 큐에 앞에 있는 값을 pop 해준다.

그리고 앞면의 개수(h)를 따로 만들어 준다.

 

4. 만약 뒷면의 개수(t)가 주어진 n과 같을 경우 반복문을 종료시킨다.

그렇지 않을 경우, k만큼 반복을 해준다. 

reversed_back 은 뒷면을 앞면으로, reversed_front 은 앞면을 뒷면으로 바꾼 개수를 각각 저장한다.

해당 값을 현재 뒷면의 개수 또는 앞면의 개수보다 오버되는 상황이 오면 continue를 시켜준다.

만약 해당 값의 경우의 수를 중복된 경우를 방지하기 위해서 visited라는 dict함수를 사용해서 

방문 표시를 하였다.

 

5. 만약 뒷면이 n이 되는 상황이 오지 않는다면, -1을 출력한다.

---

풀이 과정

import collections
n,k = map(int,input().split())
q,visited = collections.deque([[input().strip().count('T'),0]]),{}
while q :
  t,depth = q.popleft(); h = n-t
  if t == n :print(depth) ; break
  else :
    for i in range(k) :
      reversed_back = i
      reversed_front = k-i
      if reversed_back > t or reversed_front > h : continue
      if t - reversed_back + reversed_front in visited : continue
      visited[t-reversed_back+reversed_front] = True
      q.append([t-reversed_back+reversed_front,depth+1])
else : print(-1)