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

[문제 링크]

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

문제 설명

화면에 1개의 이모티콘을 3가지 연산만을 가지고 s개의 이모티콘으로 만들어서 보낸다.

 

3가지 연산

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기

3. 화면에 있는 이모티콘 중 하나를 삭제

 

 

 

 

 

문제 풀이

bfs 탐색하면서 3가지 연산을 진행하고, 현재 개수(cnt)가 s와 같으면 탐색을 종료하고 cnt를 출력한다.

2차원 배열 visited를 통해서 이미 방문한 상태를 중복해서 방문하지 않게 한다.

 

전체코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

class Emoticon {
    int clip;
    int screen;
    int cnt;

    public Emoticon(int clip, int screen, int cnt) {
        this.clip = clip;
        this.screen = screen;
        this.cnt = cnt;
    }
}

public class Main {

    static int s;
    static boolean[][] visited = new boolean[1001][1001];   //[clip][screen]

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        s = Integer.parseInt(br.readLine());

        int result = bfs();
        System.out.println(result);
    }


    public static int bfs() {
        Queue<Emoticon> q = new LinkedList<>();
        q.offer(new Emoticon(0, 1, 0));

        while (!q.isEmpty()) {
            Emoticon emo = q.poll();
            int clip = emo.clip;
            int screen = emo.screen;
            int cnt = emo.cnt;

            //종료조건
            if (screen == s) {
                return cnt;
            }

            //화면 -> 클립보드 복사
            if(!visited[screen][screen]) {
                q.offer(new Emoticon(screen, screen, cnt + 1));
                visited[screen][screen] = true;
            }
            //클립보드 -> 화면 붙여넣기
            if (clip >= 1 &&  screen + clip <= 1000 && !visited[clip][screen + clip]) {
                q.offer(new Emoticon(clip, screen + clip, cnt + 1));
                visited[clip][screen + clip] = true;
            }

            //화면에 있는 이모티콘 하나 삭제
            if (screen >= 1 && !visited[clip][screen - 1]) {
                q.offer(new Emoticon(clip, screen - 1, cnt + 1));
                visited[clip][screen - 1] = true;
            }
        }
        return 0;
    }
}

 

✔️ 체크

처음에 풀이할 때 visited 로 중복 체크를 하지 않아서 메모리 초과가 떴다.
또한 2번째 방법 클립보드 → 화면으로 붙여넣기를 할 때 화면의 이모티콘 개수(screen) + 클립보드의 이모티콘 개수(clip) 가 1000을 넘어선 안된다.(s의 최대길이가 1000)