백준 14226번 - 이모티콘

백준 14266번 - 이모티콘

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

14226번: 이모티콘

이 문제는 BFS문제(다이나믹 프로그래밍을 사용한)이다.

최근 풀었던 BFS문제중에 가장 어려웠다.

처음에는 가볍게 queue에 pair로 현재 이모티콘 숫자와 클립보드의 개수를 받아서 풀어보려 했는데

문제의 조건 중 '클립 보드에 복사'라는 조건이 자꾸 걸렸다.

생각해보다가 2차원 배열을 사용하면 될 것 같아서 써봤는데 바로 틀렸습니다..

디버깅해보니 너무 많은 문제점이 있어서 거의 처음부터 다시 풀었다.

 

결론은 2차원 배열로 풀었고, 모든 경우의 수를 탐색했다.

n제한이 1000밖에 안되기 때문에 시간 복잡도는 신경 쓰지 않았다.

 

풀이법은 먼저 queue에 집어넣을 때 구조체를 사용하여

세 가지 (현재 개수, 클립보드 개수, 이전에 복사했는지 여부)를 push 한다.

 

그리고 각 케이스 마다 3가지 경우를 탐색한다.

 

1. 클립보드에 복사하기 -> dis는 그대로 유지

2. 이모티콘을 클립보드에서 복사해오기 -> dis는 이전에 클립보드에 복사를 했는지 안 했는지를 판단 후 더해주기

3. 이모티콘 하나 제거 -> dis -= 1

 

각각의 경우마다 조건을 잘 맞춰줘야 한다. 

 

#include <iostream>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
 
int n;
int dis[1001][1001];
bool check[1001][1001];
 
struct tup {
    int a;
    int c;
    int d;
};
 
void bfs() {
    queue<tup>q;
    tup temp = { 1,0,0 };
    q.push(temp);
    check[1][0] = true;
    dis[1][0] = 0;
    while (!q.empty()) {
        int x = q.front().a;
        int clip = q.front().c;
        int pl_dir = q.front().d;
        q.pop();
        //클립보드에 복사하기
        if (x <= 1000 && x != clip && check[x][x] == false) {   
            check[x][x] = true;
            dis[x][x] = dis[x][clip];
            temp = { x,x,1 };
            q.push(temp);
        }
        //클립보드에서 화면에 이모티콘 복사하기
        if (x+clip<=1000 && clip<=1000 && check[x + clip][clip] == false) {
            check[x + clip][clip] = true;
            dis[x + clip][clip] = dis[x][clip] + 1 + pl_dir;
            temp = { x + clip,clip,0 };
            q.push(temp);
        }
        //이모티콘 하나 제거
        if (x - 1 > 0 && clip<=1000 && check[x - 1][clip] == false) {
            check[x - 1][clip] = true;
            dis[x - 1][clip] = dis[x][clip] + 1;
            temp = { x - 1,clip,0 };
            q.push(temp);
        }
    }
}
 
int main() {
    scanf("%d", &n);
    bfs();
    int ans = 100000;
    for (int i = 0; i <= 1000; i++) {
        if (dis[n][i] != 0)ans = min(dis[n][i], ans);
    }
    printf("%d\n", ans);
}

모든 경우를 찾았기 때문에 마지막에 최소 경로를 계산해서 출력해야 한다.