[Python/BOJ] 백준 14226 이모티콘_BFS

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

 

 

 

뭔가 DFS인것 같아서 DFS로 풀려고했는데 

깊이가 너무 깊다고 까였다....

 

 

정답을 찾아보니 다들 BFS로 풀이되어있었다. 

최소시간을 구하다보니 그런것 같다. 

 

 

최솟값 -> BFS 

 

 

 

3가지의 연산이 있다. 

 

1. 클립보드에 저장 

2. 클립보드의 이모티콘 화면에 저장 

3. 화면의  이모티콘 하나 삭제 

 

 

 

화면에 있는 이모티콘과 클립보드에 있는 이모티콘의 개수, 그때의 시간

이 3가지의 값을 저장하기위해서 2차원 배열을 만들어준다. 

 

 

 

행 : 현재 화면에 있는 이모티콘 개수 

열 : 클립보드의 이모티콘 개수 

값 : 시간 

 

 

 

 

bfs를 통해서 첫번째 값 (화면에는 1개, 클립보드에는 0개, 시간은 0초)에서부터 돌아준다.

사실 방법만 안다면 쉬운 문제이다. 

 

 

 

코드 : 

from collections import deque
s = int(input())

# 행은 화면의 이모티콘 개수
# 열은 클립보드에 있는 이모티콘의 개수
# 값은 시간 
vis = [[-1]*(s+1) for _ in range(s+1)]

q = deque()

def bfs() :
    # 이모티콘이 하나있고 클립보드에 0개일 때 시간은 0초 
    vis[1][0] = 0
    q.append([1,0])
    while q :
        x,y = q.popleft()
        # 클립보드로 현재 이모티콘의 개수를 덮어씌운 경우 
        if vis[x][x] == -1 :
            vis[x][x] = vis[x][y]+1
            q.append([x,x])
        # 클립보드에 있는 이모티콘을 현재 이모티콘에 붙여넣기 한 경우 
        if x+y <= s and vis[x+y][y]==-1 :
            vis[x+y][y] = vis[x][y]+1
            q.append([x+y,y])
        # 현재 이모티콘의 개수에서 1을 뺀 경우 
        if x-1 >=0 and vis[x-1][y]==-1 :
            vis[x-1][y] = vis[x][y]+1
            q.append([x-1,y])
    
bfs()
ans = int(1e9)
for i in range(s+1):
    # 이모티콘이 화면에 s개가 있는 경우 
    if vis[s][i]!= -1 :
        ans = min(ans,vis[s][i])

print(ans)

 

 

 

 

 

참고 블로그 : 

https://velog.io/@aonee/%EB%B0%B1%EC%A4%80-boj-14226-%EC%9D%B4%EB%AA%A8%ED%8B%B0%EC%BD%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] boj-14226 이모티콘 파이썬