[백준]14226: 이모티콘 - JAVA

[백준]14226: 이모티콘

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

14226번: 이모티콘

풀이

걸리는 시간의 최소값을 구하는 문제 이므로 BFS 탐색을 사용하여 문제를 풀었다.

 

BFS탐색을 하면서 조건에 맞게 1, 2, 3번을 진행하고 현재 개수가 S와 같아진다면 BFS탐색을 종료하고 현재 시간을 출력하도록 하였다.

 

탐색을 하면서 계속 같은 구간을 반복하지 않도록 visited 배열을 사용하였다. 각각의 인덱스가 의미하는 바는 [clipboard에 현재 복사된 이모티콘 개수][현재 화면에 출력된 총 이모티콘개수]이다.

 

각각의 조건을 살펴보쟈.

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

→ 현재 total개수를 clipboard로 갱신하여 큐에 담아주면 된다. 시간은 현재 시간 + 1을 해준다.

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

→ clipboard 개수는 그대로 놔두고 현재 total개수를 total + clipboard로 갱신해 큐에 담아준다. 시간은 현재 시간 + 1을 해준다.

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

→ clipboard 개수는 그대로 놔두고 현재 total개수를 total - 1로 갱신해 큐에 담아준다. 시간은 현재 시간 + 1 해준다.

 

위와 같은 조건들을 BFS탐색을 하면서 코드로 구현해 주면 된다.

 

코드

import java.util.*;
 
public class Main {
    
    static boolean[][] visited = new boolean[1001][1001];//[clipboard][total]
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int s = scan.nextInt();
        
        bfs(s);
    }
    
    public static void bfs(int s) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(0, 1, 0));
        visited[0][1] = true; 
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            if(current.total == s) {
                System.out.println(current.time);
                return;
            }
            
            // 1. 화면에 있는 이모티콘 클립보드에 저장
            q.offer(new Node(current.total, current.total, current.time + 1)); 
            
            
            // 2. 클립보드에 있는 이모티콘 붙여넣기. 
            // 클립보드 비어있지 않아야하고, 붙여넣은 후 개수가 총 개수보다 적어야 하며, 이전에 방문한적 없어야함.
            if(current.clipboard != 0 && current.total + current.clipboard <= s && !visited[current.clipboard][current.total + current.clipboard]) {
                q.offer(new Node(current.clipboard, current.total + current.clipboard, current.time + 1));
                visited[current.clipboard][current.total + current.clipboard] = true;
            }
            
            // 3. 화면에 있는 이모티콘 중 하나 삭제.
            // 총 개수 1보다 크거나 같아야하고, 방문한적 없어야함.
            if(current.total >= 1 && !visited[current.clipboard][current.total - 1]) {
                q.offer(new Node(current.clipboard, current.total - 1, current.time + 1));
                visited[current.clipboard][current.total - 1] = true;
            }
        }
    }
    
    public static class Node {
        int clipboard;
        int total;
        int time;
        
        public Node(int clipboard, int total, int time) {
            this.clipboard = clipboard;
            this.total = total;
            this.time = time;
        }
    }
}