[ProblemSolving] 백준 - 14226 이모티콘(dfs&bfs)

redcarrot01·2021년 5월 6일
0

ProblemSolving

목록 보기
34/53
post-thumbnail

문제 링크

문제 설명


영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
  3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력


첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력


첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

예제 입력1

2

예제 출력1

2

예제 입력2

4

예제 출력2

4

예제 입력3

18

예제 출력3

8

나의 풀이


bfs를 이용하여 해결했다.

bfs는 인접 노드를 먼저 방문하는 탐색인데,
다시 말하면 가까운 정점, 가까운 거리에 있는 노드를 먼저 탐색한다는 의미라서
최소비용, 최솟값 구할때 많이 활용한다.
(단, 가중치는 1이어야 한다는 전제)

check[display][board]를 하는 이유는 탐색한 곳을 다시 탐색할 필요가 없고, 최솟값을 구해야 하기 때문에 체킹을 해줘야 한다.

문제 조건처럼 나눠서 점화식을 만들어 해결했다.

초기 display = 1, board = 0, count =0으로 초기화한다.

탐색순서

  1. 화면 이모티콘을 보드에 복사 => 보드는 덮어쓰므로 화면 이모티콘 개수만큼 갖게 된다. board = display , count+= 1
  1. 클립보드 이모티콘을 화면에 추가 display += board, count +=1
  2. 화면 이모티콘-1 display -= 1 count += 1

탐색이 끝나면 count가 시간의 최솟값이다.

코드


from collections import deque

n = int(input())
max_size = 1001
check = [[-1]*max_size for _ in range(max_size)]
def bfs():
    queue = deque()
    queue.append((1, 0, 0))
    
    while queue:
        display, board, count = queue.popleft()
        
        if display == n:
            return count
        
         # 1.화면에서 보드로 저장
        if 0 < display < max_size: 
            if check[display][display] == -1:
                check[display][display] = 1
#                 count += 1
                queue.append((display, display, count+1))
                
        # 2. 보드에서 화면으로 저장, display + board 몽땅 화면에 저장되기 때문에 비교 필요    
        if 0 < board and display + board < max_size : 
            if check[display+board][board] == -1:
                check[display+board][board] = 1
                queue.append((display+board, board, count+1))
        # 3. display에서 하나 삭제
        if check[display-1][board] == -1:
            check[display-1][board] =1
            queue.append((display-1, board, count+1))

print(bfs())
            

관심 있을 만한 포스트

0개의 댓글