4. 사과 먹기 (+BFS)

DFS는 스택을 이용한 깊이 우선 탐색

BFS는 큐를 이용한 너비 우선 탐색

 

DFS를 이용한 풀이

: N이 커지면, 타임리밋 발생

-> BFS 이용하도록 변경

package Q4;

public class Main {
    public static void main(String[] args) {
//        하루 동안 먹을 수 있는 사과의 개수입니다.
//        1) 사과 한 개를 먹는다.
//        2) 현재 있는 사과의 개수가 2로 나누어 떨어지는 개수라면 그 절반(사과개수 / 2)을 먹는다. 3) 현재 있는 사과의 개수가 3으로 나누어 떨어진다면 (사과개수 / 3) * 2 개의 사과를 먹는 다.
//        현수에게 N개의 사과가 주어지면 현수가 위 3가지 중 하나를 선택해서 먹을 때 최소 몇 일만 에 사과를 모두 먹을 수 있는지
        int n=10;
        DFS(n,0);
        System.out.println(answer);
    }
    static int answer=Integer.MAX_VALUE;

    private static void DFS(int n, int L){
        //System.out.println(L+" "+n);
        if(n<=0) {
            answer=Math.min(L, answer);
            return;
        }
        if(n%2==0) DFS(n-n/2, L+1);
        if(n%3==0) DFS(n - ((n / 3) * 2), L + 1);
        DFS(n-1, L+1);
    }
}

 

---

+) 세련된 풀이

: BFS

해당 노드를 방문했는지를 체크하는 ch 변수를 배열로 잡으면 안되며 HashSet을 이용한다.

-> Set 자료구조의 경우 Map와 같은 해시구조로 검색을 수행하므로, get메서드가 존재하지 않으며 검색이 빠르다는 특징이 있다.

 

import java.util.*;
class Main {
	public int solution(int n){
		Queue<Integer> queue = new LinkedList<>();
		Set<Integer> ch = new HashSet<>();
		queue.add(n);
		ch.add(n);
		int L=0;
		while(!queue.isEmpty()){
			int len=queue.size();
			for(int i=0; i<len; i++){
				int x=queue.poll();
				if(x==0) return L;
				if(!ch.contains(x-1)){
					ch.add(x-1);
					queue.add(x-1);
				}
				if(x%2==0 && !ch.contains(x/2)){
					ch.add(x/2);
					queue.add(x/2);
				}
				if(x%3==0 && !ch.contains(x/3)){
					ch.add(x/3);
					queue.add(x/3);
				}
			}
			L++;
		}	
		return 0;
	}

	public static void main(String[] args){
		Main T = new Main();
		System.out.println(T.solution(25)); //6	
		System.out.println(T.solution(101)); //9	
		System.out.println(T.solution(1900000000)); //30
	}
}

 

package Q4;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
//        하루 동안 먹을 수 있는 사과의 개수입니다.
//        1) 사과 한 개를 먹는다.
//        2) 현재 있는 사과의 개수가 2로 나누어 떨어지는 개수라면 그 절반(사과개수 / 2)을 먹는다.
//        3) 현재 있는 사과의 개수가 3으로 나누어 떨어진다면 (사과개수 / 3) * 2 개의 사과를 먹는다.
//        현수에게 N개의 사과가 주어지면 현수가 위 3가지 중 하나를 선택해서 먹을 때 최소 몇 일만 에 사과를 모두 먹을 수 있는지
        //int n=10;
        int n=1900000000;
        System.out.println(BFS(n,0));
    }
    static int answer=Integer.MAX_VALUE;

    private static int BFS(int n, int L){
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> s = new HashSet<>();
        q.add(n);
        s.add(n);
        //BFS 특징: 큐의 사이즈만큼 반복문 수행
        while(!q.isEmpty()){
            int len=q.size();
            for(int i=0;i<len;i++){
                int x=q.poll();
                // x==0이면 리턴
                if(x==0) return L;
                //최소 일자를 찾아야하므로, 이미 가능한 날짜는 제외
                if(!s.contains(x-1)){
                    s.add(x-1);
                    q.offer(x-1);
                }
                if(x%2==0&&!s.contains(x/2)){
                    s.add(x/2);
                    q.offer(x/2);
                }
                if(x%3==0&&!s.contains(x/3)){
                    s.add(x/3);
                    q.offer(x/3);
                }
            }
            L++;
        }
        return L;
    }
}