[DFS/BFS/완전탐색] 14226번 - 이모티콘

[백준] 14226번 - 이모티콘

풀이 시간: 70분 이내

 

1) 문제 해결 아이디어

문제 아이디어를 떠올리고 구현을 하는 것 자체는 30분도 안걸렸는데 오류를 고치느라 시간이 오래걸렸다.

초기 화면에 이모티콘 1개가 입력된 상태에서 3가지 연산을 이용해 이모티콘을 S개를 만드는데 걸리는 최소 시간을 구하는 문제다. 최소 시간을 구하는 문제이니 BFS를 이용하였고 이 문제를 푸는데 중요한 포인트는 3가지 연산을 수식화하는 것이다!!

 

<3가지 연산>

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.

(screen, board) → (screen, screen)

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.

(screen, board) → (screen + baord, board)

3. 화면에 있는 이모티콘 중 하나를 삭제한다.

(screen, board) → (screen - 1, board)

 

첫번째 오류. 메모리 초과

원래는 방문 여부를 체크하는 graph를 선언하지 않고 화면, 클립보드의 범위만 검사하여 모든 경우에 대해 큐에 담기도록 했다. 입력되는 수가 작을 때는 별 문제가 되지 않지만 그 수가 커지면 메모리 초과가 발생한다. 이렇게 되면 중복된 쌍들에 대해서 또 똑같은 것을 반복 수행하게 된다.

그래서 방문한 (화면, 보드) 쌍은 큐에 삽입하지 않게 하기 위해 방문 여부를 검사하는 graph를 집합으로 생성하였다.

 

Q. graph를 리스트가 아닌 집합으로 생성한 이유는?

다른 제출 코드에 비해 수행 시간이 거의 10배 정도로 길어서 시간 단축을 위해 방문 여부를 체크하하는 것으로 리스트가 아닌 집합을 사용하였다.

아래 문제도 시간 초과로 방문한 곳을 담는 것을 리트스가 아닌 집합으로 생성하여 문제를 해결한 케이스로 시간 초과 문제가 있다면 리스트가 아닌 집합을 이용하는 것을 기억하자!!!

 

[참고] https://hseungyeon.tistory.com/228

[DFS/BFS/완전탐색] ▲ 5014번 - 스타트링크(BFS)

 

2) 소스코드

from collections import deque

# BFS
def bfs(screen, board, time):
  queue = deque()
  # 시작점 삽입, 방문 처리
  queue.append((screen, board, time))
  graph.add((screen, board))
  
  while queue:
    screen, board, time = queue.popleft()
    # 화면의 이모티콘 개수가 목표치에 도달하면
    if(screen == s):
      return time

    # 화면과 클립보드 수가 범위 내이고 
    # (화면, 보드) 쌍이 방문한 적이 없으면 
    # 큐에 (화면, 보드, 시간) 쌍 삽입, 그래프에 (화면, 보드) 쌍 삽입
    # 1. 화면에 있는 모든 이모티콘을 클립보드에 저장
    if(1 <= screen <= 1000):
      if((screen, screen) not in graph):  
        queue.append((screen, screen, time + 1))
        graph.add((screen, screen))
    # 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기
    if(1 <= screen + board <= 1000 and 0 < board):
      if((screen + board, board) not in graph):
        queue.append((screen + board, board, time + 1))
        graph.add((screen + board, board))
    # 3. 화면에 있는 이모티콘 중 하나를 삭제
    if(1 <= screen - 1 <= 1000):
      if((screen - 1, board) not in graph):
        queue.append((screen - 1, board, time + 1))
        graph.add((screen - 1, board))

s = int(input())  # 이모티콘 개수
graph = set()     # 방문한 (화면, 보드) 쌍을 담을 집합
print(bfs(1, 0, 0))  # 화면 이모티콘 1, 클립보드 이모티콘 0개, 시간 0으로 시작