[백준][14226번] 이모티콘

문제 URL

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

BFS

BFS를 이용해 해결할 수 있는 문제는 아래와 같은 조건을 만족해야한다.

1. 최소 비용문제이어야 한다.
2. 간선의 가중치가 1이어야 한다.
3. 정점과 간선의 개수가 적어야한다.(적다는 것은 문제의 조건에 맞춰서 해결할수있다는 것을 의미)
   • 간선의 가중치가 문제에서 구하라고 하는 최소 비용과 의미가 일치해야한다.
   • 즉, 거리의 최소값을 구하는 문제라면 가중치는 ‘거리’를 의미하고 시간의 최소값을 구하는 문제라면 가중치는 ‘시간’을 의미

전체 풀이

S개의 이모티콘을 만드는데 걸리는 시간의 최소값을 구하는 문제다.

• BFS에서 하나의 정점이 서로 다른 두개의 정보를 저장하고 있으면 안된다.
• 화면에 있는 이모티콘의 개수가 5개인 경우
• 클립보드에 있는 이모티콘의 개수에 따라서, 클립보드에서 복사하기 연산의 결과가 다르다.

• 즉, 화면에 이모티콘의 개수 S와 클립보드에 있는 이모티콘의 개수 C가 중요하다.

• 연산방법 복사 : (S,C) -> (S,S) 붙여넣기 : (S,C) -> (S+C,C) 삭제 : (S,C) -> (S-1,C)

2<=S<=1000이므로 BFS 탐색가능하다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static class Pair {
        public int x;
        public int cb;

        public Pair(int x, int cb) {
            this.x = x;
            this.cb = cb;
        }
    }

    public static final int MAX = 1001;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int[][] d = new int[MAX][MAX];

        for (int i = 0; i < MAX; i++) {
            Arrays.fill(d[i], -1);
        }

        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(1, 0));
        d[1][0] = 0;

        while (!q.isEmpty()) {
            Pair p = q.remove();

            if (d[p.x][p.x] == -1) {
                d[p.x][p.x] = d[p.x][p.cb] + 1;
                q.add(new Pair(p.x, p.x));
            }

            if ((p.x + p.cb < MAX) && d[p.x + p.cb][p.cb] == -1) {
                d[p.x + p.cb][p.cb] = d[p.x][p.cb] + 1;
                q.add(new Pair(p.x + p.cb, p.cb));
            }

            if ((p.x - 1 >= 0) && d[p.x - 1][p.cb] == -1) {
                d[p.x - 1][p.cb] = d[p.x][p.cb] + 1;
                q.add(new Pair(p.x - 1, p.cb));
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < MAX; i++) {
            if (d[s][i] != -1) {
                min = Math.min(min, d[s][i]);
            }
        }

        System.out.println(min);
    }
}