[백준 문제풀이] 14226번 : 이모티콘

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

14226번: 이모티콘

 

💡dfs를 사용해서 클립보드를 탐색하는 문제였다. 화면의 이모티콘 개수와 클립보드에 복사된 이모티콘 개수가 함께 필요하기 때문에 2차원 배열을 사용해주었다. 

 

각 조건에 맞게 if문을 작성하고, for문을 돌면서 결과값을 계산한다.

쉬울 줄 알았는데 생각보다 어려웠던 문제..

 

✔소스코드

import sys
from collections import deque
N=int(sys.stdin.readline())
visited=[[-1]*(N+1) for i in range(N+1)]

def dfs():
    q=deque()
    q.append((1,0))
    visited[1][0]=0
    while q:
        a,b=q.popleft()
        if visited[a][a]==-1:
            visited[a][a]=visited[a][b]+1
            q.append((a,a))
        if a+b<=N and visited[a+b][b]==-1:
            visited[a+b][b]=visited[a][b]+1
            q.append((a+b,b))
        if a-1>=0 and visited[a-1][b]==-1:
            visited[a-1][b]=visited[a][b]+1
            q.append((a-1,b))
    result=-1
    for i in range(N+1):
        if visited[N][i]!=-1:
            if result==-1 or result>visited[N][i]:
                result=visited[N][i]
    print(result)

dfs()