[Algorithm] 백준_14226번: 이모티콘

오늘의 추가 문제는 🚀 백준 14226 이모티콘 이다.

BFS를 뿌셔보자라는 마음으로 열심히 풀었다.

테스트케이스 이해하기

위 쓰여있는 것처럼 세가지 경우가 있는데, 이 케이스를 활용해서 원하는 이모티콘 갯수만큼 만드는 문제이다.

알고리즘

이번 문제를 풀면서 BFS의 문제의 정점과 간선을 설정하는게 얼마나 중요한지 배울 수 있었다.

1. x= 화면 이모티콘 갯수, y=클립보드 이모티콘 갯수 즉 각각의 정점으로 설정했다.
2. 화면 이모티콘을 복사 했을 경우는 x, x를 q에 append 했고,
3. 클립보드에 있는 이모티콘을 화면에 복사 했을 경우는 x+y, y를 append
4. 화면 아이콘 하나 삭제했을 경우는 x-1, y를 append 해서 q를 돌렸다.
5. 화면에 있는 이모티콘 x가 목표한 n과 같으면 break해서 탈출하였다.

정점과 간선을 설정을 못해서… 처음에 완전 이상하게 풀어서 해결을 못했다.

인강을 들으니.. x= 화면 이모티콘 갯수, y=클립보드 이모티콘 갯수로 설정하시더라!

그래서 아! 하고 풀어보니 금방 풀렸다. 역시 처음 단추를 어떻게 끼우는가가 알고리즘 문제 풀때 가장 중요한 것 같다.

정답코드

from collections import deque
#BFS는 정점과 간선이 무엇인지 정확히 정하고 가야한다.
# x= 화면 이모티콘 갯수, y=클립보드 이모티콘 갯수

max =2000
n = int(input())
arr=[[0]*max for _ in range(max)]


window = deque()
clip = deque()

window.append(1)
clip.append(0)

while window:
    x = window.popleft()
    y = clip.popleft()

    if x == n:
        print(arr[x][y])
        break
        #화면에 있는 이모티콘 복사
    if -1< y+x <max and arr[x][x] == 0:
        arr[x][x]= arr[x][y] +1
        window.append(x)
        clip.append(x)

        #클립보드에 있는 이모티콘을 화면에 복사
    if -1< x+y <max and arr[y+x][y] ==0:
        arr[y+x][y]= arr[x][y] +1
        window.append(x+y)
        clip.append(y)

        #화면 아이콘 하나 삭제
    if -1 < x-1 < max and arr[x-1][y] ==0 :
        arr[x-1][y]= arr[x][y] +1
        window.append(x-1)
        clip.append(y)



# for i in range(10):
#     print(' '.join(map(str, arr[i])))

🚀Reference: 백준 14226 이모티콘