14226번 - 이모티콘(bfs)

문제:

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

 

 

풀이:

시간의 최솟값을 찾는 경우이므로 bfs()를 이용한다.
저장해야 하는 값이 3개나 있으므로 이를 위해 클래스를 하나 작성하였다.

class Imo {
    int count;
    int clipboard;
    int time;
    public Imo(int count, int clipboard, int time){
        this.count = count;
        this.clipboard = clipboard;
        this.time = time;
    }
}

count는 이모티콘의 개수, clipboard는 클립보드에 복사된 이모티콘의 개수이며, time은 시간을 나타낸다.

public class 이모티콘_14226번 {
    static int S;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.nextInt();
        visited = new boolean[S*2][S*2];

        System.out.println(bfs());

    }

    static int bfs() {
        Queue<Imo> queue = new LinkedList<>();
        queue.add(new Imo(1, 0, 0));
        visited[1][0] = true;

        while (!queue.isEmpty()) {
            Imo imo = queue.poll();
            int count = imo.count;
            int clipboard = imo.clipboard;
            int time = imo.time;
            if (count == S) {
                return time;
            }
            // 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
            if (clipboard > 0 && count + clipboard < S*2 && !visited[clipboard+count][clipboard]) {
                visited[count + clipboard][clipboard] = true;
                queue.add(new Imo(count + clipboard, clipboard, time + 1));
            }
            // 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
            if (count > 0 && count < S*2 && !visited[count][count]) {
                visited[count][count] = true;
                queue.add(new Imo(count, count, time + 1));
            }
            // 화면에 있는 이모티콘 중 하나를 삭제한다.
            if (count > 0 && !visited[count - 1][clipboard]) {
                visited[count - 1][clipboard] = true;
                queue.add(new Imo(count - 1, clipboard, time + 1));
            }
        }

        return -1;
    }
}

visited를 이차원 배열로 저장한 이유는, 클립보드라는 특수한 조건 때문이다.

특정 개수의 이모티콘이 입력되어 있고(count), 클립보드에 특정 개수의 이모티콘이 저장되어 있다(clipboard).

동일한 이모티콘이 입력되어 있어도, 클립보드에 저장될 수 있는 이모티콘의 수는 정해지지 않는다.

고로 이차원 배열을 이용해, count와 clipboard 모두 겹치는 상황만 피해주면 된다.

예를 들어 1 -> 5에 도달한다고 가정하자.

만일 visited가 1차원 배열이라면, (1,0,0) -> (0,0,1) 이후 갈 수 있는 곳이 없을 뿐더러,
3을 클립보드에 저장하고 다시 2로 되돌아오는 경우는 생각하지 못한다.

고로 visited[][]가 필요하다.

 

bfs() 메서드는 숨바꼭질 2, 3, 4에서 작성했던 bfs와 상당히 유사하다.

while문의 조건이 큐가 비어있지 않는동안 반복이지만, 그전에 무조건 return 되기에 큰 의미는 없다.

너무 많이 설명한 방식이라 생략하겠다. 위 메서드에 대한 설명은 아래 블로그를 보면 이해 할 수 있을 것이다.

13913번 - 숨바꼭질4(bfs) (tistory.com)

 

전체코드:

import java.util.*;

class Imo {
    int count;
    int clipboard;
    int time;
    public Imo(int count, int clipboard, int time){
        this.count = count;
        this.clipboard = clipboard;
        this.time = time;
    }
}

public class 이모티콘_14226번 {
    static int S;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.nextInt();
        visited = new boolean[S*2][S*2];

        System.out.println(bfs());

    }

    static int bfs() {
        Queue<Imo> queue = new LinkedList<>();
        queue.add(new Imo(1, 0, 0));
        visited[1][0] = true;

        while (!queue.isEmpty()) {
            Imo imo = queue.poll();
            int count = imo.count;
            int clipboard = imo.clipboard;
            int time = imo.time;
            if (count == S) {
                return time;
            }
            // 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
            if (clipboard > 0 && count + clipboard < S*2 && !visited[clipboard+count][clipboard]) {
                visited[count + clipboard][clipboard] = true;
                queue.add(new Imo(count + clipboard, clipboard, time + 1));
            }
            // 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
            if (count > 0 && count < S*2 && !visited[count][count]) {
                visited[count][count] = true;
                queue.add(new Imo(count, count, time + 1));
            }
            // 화면에 있는 이모티콘 중 하나를 삭제한다.
            if (count > 0 && !visited[count - 1][clipboard]) {
                visited[count - 1][clipboard] = true;
                queue.add(new Imo(count - 1, clipboard, time + 1));
            }
        }

        return -1;
    }
}

 

 

시행착오:

처음에는 visited[]를 이용했다. 물론 될 리는 없었다.

이후에는 굳이 visited[]를 이용할 이유가 있을까라는 이상한 생각을 해서 메모리가 초과되었다.

문제를 푼 이후에도 실수가 있었는데, 무슨 이유에서인지 우선순위 큐를 이용하고 있었다.

자꾸 bfs에서 우선순위 큐를 쓰려는 안좋은 습관이 있는듯 하다.

이 기회에 이 이상한 습관을 고쳐보도록 하자. ㅜ