알고리즘 풀이 - 백준 14226(이모티콘, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

이모티콘을 복사, 붙여넣기, 1개 삭제가 가능할 때, S개의 이모티콘이 화면에 나타나는데 필요한 최소 시간을 구하는 문제

 

 

2. 풀이

 

이모티콘이 화면에 N개가 주어지게 할 때 실행하는 연산의 최소 경우를 구하는 문제이다. 각 연산 마다 1초가 소요되므로 연산의 수는 시간과 동일하다.

이모티콘은 2가지의 경우가 있다.

① 화면에 출력된 이모티콘의 수
② 클립보드에 복사된 이모티콘의 수

 

그러므로, 현재 상태값을 저장할 배열은 2차원으로 구성하여 화면 출력된 수와 복사된 이모티콘의 수를 저장하며 탐색을 수행하면 된다.

탐색은 BFS를 통해 수행한다. 왜냐면, BFS로 진행 시 각 경우에 최소 시간이 보장되는 탐색 방법이기 때문이다.

 

연산은 다음의 3가지가 있다.

① 클립보드의 이모티콘을 화면에 복사
  - 현재 클립보드에 1개 이상의 이모티콘이 있고, 해당 경우가 이미 이전에 진행되지 않았으며, 붙여넣었을 때 화면 상 이모티콘의 개수가 1000개 이하일 때 가능

② 화면에 있는 것을 클립보드에 복사
  - 화면과 클립보드 이모티콘 개수가 다르고, 해당 경우가 이미 이전에 진행되지 않은 경우 가능

③ 화면에 있는 이모티콘 1개를 삭제
  - 화면에 이모티콘이 1개 이상 있고, 해당 경우가 이미 이전에 진행되지 않은 경우 가능

 

위 3가지의 연산을 통해 탐색을 수행하고 화면에 출력된 이모티콘의 수가 주어진 수와 같으면 탐색을 그만 둔다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

public class Main{
    static int s;
    static boolean[][] visited = new boolean[2001][2001];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = Integer.parseInt(br.readLine());
        Queue<Emo> q = new LinkedList<>();
        
        // 최초 화면 상 1개, 클립보드에 0개 있는 상태를 넣는다. 0초 상태
        q.offer(new Emo(1, 0, 0));
        visited[1][0] = true;
        
        int ans = 0;
        while(!q.isEmpty()){
            Emo e = q.poll();
            if(e.screen == s){
                ans = e.time;
                break;
            }
            
            // 현재 클립보드에 있는 것을 화면에 붙여넣는다.
            // 클립보드에 있는 값이 0이 아니고 화면 복사 시의 경우가 이미 진행된 경우가 아니며
            // 화면 출력 되는 개수가 1000이하인 경우에 가능
            if(e.clip != 0 && !visited[e.screen + e.clip][e.clip] && e.screen + e.clip <= 1000){
                q.offer(new Emo(e.screen + e.clip, e.clip, e.time+1));
                visited[e.screen+e.clip][e.clip] = true;
            }
            
            // 현재 화면에 있는 것을 클립보드에 복사한다.
            // 화면과 클립보드의 이모티콘 개수가 다르고 복사 시의 상태가 이미 진행된 경우가 아닌 경우
            if(e.screen != e.clip && !visited[e.screen][e.screen]){
                q.offer(new Emo(e.screen, e.screen, e.time+1));
                visited[e.screen][e.screen] = true;
            }
            
            // 현재 화면에 있는 이모티콘 1개를 삭제한다.
            if(e.screen > 0 && !visited[e.screen-1][e.clip]){
                q.offer(new Emo(e.screen-1, e.clip, e.time+1));
                visited[e.screen-1][e.clip] = true;
            }
        }
        System.out.println(ans);
        br.close();
    }
}

class Emo{
    int screen;
    int clip;
    int time;
    public Emo(int screen, int clip, int time){
        this.screen = screen;
        this.clip = clip;
        this.time = time;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.