[알고리즘] BOJ 14226번 - 이모티콘(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

9 / 50

 

탐색

11 / 50(NEW!)

 

기초 동적 프로그래밍

9 / 50

---

투포인터

2 / 10

 

이분탐색

0 / 10

---

문제

14226번: 이모티콘

→ solved.ac 기준 골드 4

---

문제 해결 아이디어

최소 경로를 구하는 문제로, BFS를 이용

 

⇒ 스크린에 있는 이모티콘의 갯수(screen)와 클립보드에 있는 이모티콘의 갯수(clip)를 방문하면서 큐에 담고, 최소 경로를 기록하자.

 

⇒ screen과 clip을 queue에서 꺼내면, 각각의 3가지 경우에 대해서 방문한다.

방문하는 그래프는 2차원 배열로 만든다.

graph[i][j] == i개가 화면에 있으며 동시에 j개가 클립보드에 있는 경우를 나타낸다.

 

⇒ 3가지 경우에 대한 방문 방법

 

1. 화면에 있는 이모티콘을 복사해서 저장하는 경우

현재 화면에 있는 이모지를 클립보드에 저장하는 시간 = :이전 상태, 즉 현재 화면에서 현재 클립보드 저장하는 시간 + 1

graph[screen][screen] = graph[scrren][clip] + 1

그리고 다음 차례에 screen, screen에 방문

 

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

graph[screen + clip][clip] = graph[screen][clip] + 1

다음 차례에 screen + clip, clip에 방문

 

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

graph[screen - 1][clip] = graph[screen][clip] + 1

다음 차례에 screen - 1, clip에 방문

---

구현

내 풀이

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
  queue = deque()
  queue.append((1, 0))
  # 스크린에 있는 이모티콘 갯수(복사 or 지우기 가능) / 클립보드에 있는 이모티콘 갯수(붙여넣기 가능)
  while queue:
    screen, clip = queue.popleft()
    # 1. 화면에 있는 이모티콘을 복사해서 저장
    if screen > 0 and screen < s + 1 and graph[screen][screen] == -1:
      graph[screen][screen] = graph[screen][clip] + 1
      queue.append((screen, screen))
    # 2. 클립 보드에 있는 모든 이모티콘을 화면에 붙여넣기
    if screen > 0 and screen < s + 1 and clip > 0 and clip < s + 1 and screen + clip < s + 1 and graph[screen + clip][clip] == -1:
      graph[screen + clip][clip] = graph[screen][clip] + 1
      queue.append((screen + clip, clip))
    # 3. 화면에 있는 이모티콘 중 하나를 삭제
    if screen - 1 > 0 and screen < s + 1 and graph[screen - 1][clip] == -1:
      graph[screen - 1][clip] = graph[screen][clip] + 1
      queue.append((screen - 1, clip))

  result = graph[s][1]
  for i in range(1, s):
    if graph[s][i] != -1:
      result = min(result, graph[s][i])
  return result
  
s = int(input())

graph = [[-1] * (s + 1) for _ in range(s+1)]
graph[1][0] = 0 # graph[화면에 있는 이모티콘 갯수][클립보드에 있는 이모티콘 갯수]

print(bfs())

---

메모

• 걸린 시간: 1시간 30분
  • 그러나 1트에 못 품 + 다른 사람 풀이 참고했기 때문에 ... 다음에 또 풀어볼 것.
• 처음에 클립보드에 저장하는 시간을 따로 만들자고 생각해서 1차원 배열을 2개 만들었는데... 도저히 풀 수가 없었음..
  • 탐색 시에 그래프를 상태로 보고 한다면 2차원 배열로도 할 수 있구나,,

---