[BOJ/JAVA] 백준 14226번 : 이모티콘

14226번: 이모티콘

---

 

• 생각

문제를 읽었을 때, dp문제였지만 bfs 방식을 사용해도 될 것같았다. (시간안에 들어올지가 문제인데 넉넉할 것 같다고 판단함)

bfs를 사용해서 모든 경우의수로 이동해보면서 해당하는 숫자에 도달했을때 depth를 구했다.

방문 처리를 2차원배열로 해서 현재개수와 클립보드에 저장된 갯수 두가지로 체크하면서 이동했다.

 

dp방식은 잘 모르겠다..ㅜ (dp 방식으로 풀어본 사람을 찾아보려했는데 java로 푼 사람중에 dp로 푼 사람이 없었다.)

 

• 코드

정답 코드 : bfs방식으로 구현하였다. 

 

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

public class Main {
	private static int S, answer;
	private static boolean[][] check;

	public static void main(String[] args) throws Exception {
		SetData();
		bfs();
		System.out.println(answer);
	}
	
	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		S = Integer.parseInt(br.readLine());
		check = new boolean[1001][1001];	
		answer = 0;
	}
	
	private static void bfs() {
        Queue<int []> queue = new LinkedList<>();
        queue.offer(new int[] {1,1,1});
        check[1][1] = true;
        
        while(!queue.isEmpty()){
        	int location[] = queue.peek();
            
            if(location[0] == S){
                answer = location[2];
                break;
            }
            
            if(location[0] - 1 != 0 && !check[location[0] - 1][location[1]]){
                queue.offer(new int[] {location[0] - 1, location[1], location[2] + 1});
                check[location[0] - 1][location[1]] = true;
            }
            
            if(!check[location[0]][location[0]]){
                queue.offer(new int[] {location[0], location[0], location[2] + 1});
                check[location[0]][location[0]] = true;
            }
            
            if(location[0] + location[1] <= S && !check[location[0] + location[1]][location[1]]){
            	queue.offer(new int[] {location[0] + location[1], location[1], location[2] + 1});
                check[location[0] + location[1]][location[1]] = true;
            }
            
            queue.poll();
        }
	}
}