[Backjoon] 골드 4 이모티콘

문제: 이모티콘

https://www.acmicpc.net/problem/14226

풀이코드

from collections import deque

S = int(input())
visited = [[False] * 1001 for _ in range(1001)] ## S의 최대값이 1001
## visited 행: 화면 이모티콘 개수, visited 열: 클립보드 이모티콘 개수
## visited[화면개수][클립보드개수]

q = deque()

q.append((1, 0, 0))  ## (화면, 클립보드, 시간)
visited[1][0] = True

while q:
    s, c, t = q.popleft()
    
    if s == S:
        print(t)
        break
        
    ## copy
    if s != c and not visited[s][s]: 
        visited[s][s] = True
        q.append((s, s, t+1)) 
    ## paste
    if c > 0 and s+c <= 1000 and not visited[s+c][c]:
            visited[s+c][c] = True
            q.append((s+c, c, t+1))
    ## delete
    if s > 1 and not visited[s-1][c]: 
            visited[s-1][c] = True
            q.append((s-1, c, t+1))

---

느낀 점

화면의 이모티콘 개수, 클립보드의 이모티콘 개수를 계속 반복해서 했던 거 또하고 하면 안 되기 때문에

visited 행렬을 사용하면 좋을 것이라고 생각했다.

(화면의 이모티콘 개수, 클립보드의 이모티콘 개수)를 행과 열로 놓고 이 상황에 놓일 때마다 visited[화면의 이모티콘 개수][클립보드의 이모티콘 개수] = True로 바꿔주어 다음에 그 상황에 안 갈 수 있또록 해주었다. 

 

또한 전체 상태인 시간까지 합쳐서 queue로 놓고 만약 목표 이모티콘 수에 달하면 시간을 출력해주었다. 

 

그 후 연산의 조건에서 좀 많이 헤맸다. 

내가 헷갈린 부분은 다음과 같다. 

 

1. 나는 s > c 인 경우에만 copy를 해주어야 한다고 생각했다. 

예시: 화면=2, 클립보드=3인 상황
조건: 2 < 3 → False → 복사 안함
BUT 복사하면: 화면=2, 클립보드=2가 됨
이후 붙여넣기: 화면=4, 클립보드=2 (유용한 상태가 될 수 있음!)

때문에 c != s 일 때 다 해보는 걸로 수정했다. 

 

2. 나는 s <= c 인 경우에만 paste 연산이 유용하다고 생각했다. 

하지만 내가 간과한 것은 화면에 이모티콘이 0개일 때였다. 처음부터 이모티콘이 1개가 놔져있어서 0개가 될 일은 없다고 생각했지만 생각해보면 delete 연산도 있어서 0개를 생각해주어야 했다. 

때문에 c > 0 인 것으로 수정했다. 

 

3. 나는 s > S일 때만 delete 연산을 수행해야 한다고 생각했다. 

예시: S=10을 만드는 과정에서 화면=8인 상황
조건: 8 > 10 → False → 삭제 안함
삭제 후: 화면=7 → 복사 → 클립보드=7 → 붙여넣기 → 화면=14 → 삭제들 → 10 달성!

그렇다. 내가 계속 잘못 생각하고 있었던 건 유용할 때만이었는데 그것도 모든 상황을 고려 못한 것이었고 BFS였기 때문에 모든 상황을 고려해야 한 것이다. 

때문에 이 조건도 s > 1일 때로 바꿔주었다.