백준 14226. 이모티콘

풀이

bfs 순회를 하면서 핵심은 이중 리스트로 방문처리를 해야한다는 것입니다.

visited[화면 이모티콘 개수][클립보드 이모티콘 개수] 로 방문처리를 합니다.

범위를 넘어가는 값에 대해서는 더 이상 진행하지 않는 것도 핵심입니다.

 

import sys
from collections import deque

MAX = 1000 # 최대 화면 이모티콘 수 (2 <= len(S) <= 1000)

S = int(input())

q = deque()
q.append((1,0,0)) # 화면 이모티콘, 클립보드 이모티콘, 카운트

visited = [[False]* (MAX+1) for _ in range(MAX+1)] # 방문 표시 배열 (1000까지 가능)
visited[1][0] = True # 초기화


while q:
    screen, clipboard, count = q.popleft() # 화면 이모티콘, 클립보드 이모티콘, 카운트

    if screen == S: # 만약 화면에 이모티콘의 개수가 같다면
        print(count)
        break # 탈출

    for i in range(3):
        if i == 0:
            # 이모티콘 복사하여 클립보드에 저장
            new_screen, new_clipboard = screen, screen
        elif i == 1:
            # 클립보드에 있는 모든 이모티콘 화면에 붙이기
            if not clipboard:
                continue
            new_screen, new_clipboard = screen + clipboard, clipboard
        elif i == 2:
            # 화면에 있는 이모티콘 중 하나를 삭제
            new_screen, new_clipboard = screen -1, clipboard
        
        # 화면 이모티콘의 범위를 만족하며, 방문하지 않았을 경우
        if 0 < new_screen <= MAX and not visited[new_screen][new_clipboard]:
            q.append((new_screen, new_clipboard, count +1)) # 추가
            visited[new_screen][new_clipboard] = True # 방문 표시

 

정리

생각해내는 것이 쉽지 않았던 문제인 만큼 문제를 분석해야한다.

다음 일을 처리하기 위해서 (화면 이모티콘, 클립보드 이모티콘) 조합이 필요하면 이를 2차원 배열로 방문표시하면 된다.

예) 만약 3개의 조합이다? => 3차원 배열

 

✔ bfs 문제

1. visited 배열의 요소 (몇 개로 구성하면 좋을지: 차원의 수)

2. 범위

를 어떻게 구성하면 좋을지를 먼저 생각해보자