[백준 14226번] 이모티콘 - 파이썬

문제 링크:

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

14226번: 이모티콘

 

---

풀이 유형:

다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

풀이 과정:

이 문제는 다이나믹 프로그래밍(DP)로 풀지 않고 딕셔너리를 이용한 bfs로 풀었다.

bfs 대부분의 문제는 방문 표시를 가능한 전체 인덱스 수만큼 만들어서 해결하는데, 이 문제는 다르다.

이 문제는 현재 이모티콘의 개수와 클립보드에 있는 이모티콘 개수 2가지를 이용해 bfs로 풀어야 한다.

 

방문 표시를 2차원 리스트로 만들면 되지 않나요?? 궁금증이 있으신 분들이 있을 것이다.

하지만 2차원 리스트로 만들면 불필요한 정보들이 많기에  코드를 실행하는데 시간 소요가 많이 든다.

 

풀이 코드에서 visited[now][clip]은 now는 현재 이모티콘 개수, clip은 클립보드 이모티콘 개수를 의미한다.

이모티콘을 만드는데 총 3가지 연산이 있기 때문에 이를 각각 실행해주면 된다.

 

 

풀이 코드:

# 14226번 이모티콘

from collections import deque

s = int(input())
q = deque()
# (현재 이모티콘 개수, 클립보드에 있는 개수)
q.append((1, 0))
# 2차원 리스트를 만들 수 있으나 불필요한 정보가 많으므로 방문 표시를 딕셔너리로 표현
visited = dict()
visited[(1, 0)] = 0

# 너비 우선 탐색 실행
while q:
    now, clip = q.popleft()
    # 현재 이모티콘 개수가 s개라면
    if now == s:
        # 걸린 시간 출력
        print(visited[(now, clip)])
        break
    # 1. 화면에 있는 이모티콘을 모두 복사하기
    if (now, now) not in visited.keys():
        visited[(now, now)] = visited[(now, clip)] + 1
        q.append((now, now))
    # 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기
    if (now + clip, clip) not in visited.keys():
        visited[(now + clip, clip)] = visited[(now, clip)] + 1
        q.append((now + clip, clip))
    # 3. 화면에 있는 이모티콘 중 하나를 삭제하기
    if (now - 1, clip) not in visited.keys():
        visited[(now - 1, clip)] = visited[(now, clip)] + 1
        q.append((now - 1, clip))

 

 

14226 이모티콘