BOJ 14226 · 이모티콘

알고리즘 분류 : BFS  

S개의 이모티콘을 화면에 만드는 데 걸리는 최소 시간을 구하는 문제다. 3개의 동작이 있고, 각 동작은 1초가 걸리며, 이 동작의 최소 횟수를 구하는 문제이므로, BFS 풀이로 접근할 수 있다.

• 방문(상태) 체크를 하기 위해서, 2차원 배열이 필요하다.
• 2차원 배열의 인덱스는 [화면에 있는 이모티콘] [클립보드에 있는 이모티콘] 이다.
• 화면에 있는 이모티콘을 x, 클립보드에 있는 이모티콘을 y라 했을 때, 현재 상태를 (x, y)라 하자.
• 다음 상태는 다음과 같다.
• 1. 복사 (x, x)
• 2. 붙여넣기 (x+y, y)
• 3. 삭제 (x-1, y)
• 위 3가지를 기준으로 BFS를 돌려서 최소 시간을 구하면 된다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

struct emoji {
    int x, y;
};

int s;
int dist[2001][2001];

void bfs() {
    queue<emoji> q;
    q.push({1, 0});
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        if (x == s) {
            printf("%d\n", dist[x][y]);
            return;
        }
        int nx[] = {x, x+y, x-1}, ny[] = {x, y, y};
        for (int i=0; i<3; i++) {
            if (nx[i] < 0 || nx[i] > 2*s) continue;
            if (dist[nx[i]][ny[i]]) continue;
            q.push({nx[i], ny[i]});
            dist[nx[i]][ny[i]] = dist[x][y]+1;
        }
    }
}

int main() {
    scanf("%d", &s);
    bfs();
    return 0;
}

---

Python 3 소스코드

from collections import deque

s = int(input())*2
dist = [[0]*s for _ in range(s)]

def bfs():
    q = deque()
    q.append((1, 0))
    while q:
        x, y = q.popleft()
        if x == s//2:
            print(dist[x][y])
            return
        for nx, ny in (x, x), (x+y, y), (x-1, y):
            if nx < 0 or nx > s:
                continue
            if not dist[nx][ny]:
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y]+1

bfs()

---

참고

• 백준 온라인 저지 : BOJ 14226