[BOJ]14226 : 이모티콘

문제

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

 

사용 알고리즘

BFS

 

풀이

1. visited 관리

- 현재 스티커의 갯수 뿐만 아니라 클립보드에 있는 스티커 수 별로도 시간이 달라지기 때문에 2차원 배열로 관리

- 이미 방문한 곳을 계속 방문하지 않기 위해 사용

2. bfs

- 동일한 가중치를 가지는 그래프에서 최단 경로를 찾는 데 유리

- BFS는 보통 모든 경우를 탐색하기 때문에, 경우의 수가 많을 때는 비효율적일 수 있지만, S의 최대값이 1000이므로, BFS로 충분히 해결 가능하다고 판단

+ heapq 를 사용한 다익스트라 알고리즘은 가중치가 다른 경로에서 최단 경로를 찾을 때 사용

+ 이 문제에서 각 연산은 동일한 비용(1초)을 가지므로, 다익스트라보다 BFS가 더 간단하고 효율적이라고 판단하여 BFS 선택

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
q = deque([(1, 0)])  # (cur, clip)
visited = [[0] * 1001 for _ in range(1001)]
cnt = 0

while q:
    cur, clip = q.popleft()

    if cur == N:
        print(visited[cur][clip])
        break

    arr = [(cur, cur), (cur + clip, clip), (cur - 1, clip)]

    for c, v in arr:
        if 0 < c < 1001 and 0 <= v < 1001 and visited[c][v] == 0:

            q.append((c, v))
            visited[c][v] = visited[cur][clip] + 1

 

 

결과