송아지 찾기 BFS

넓이 우선 탐색문제이다

만약 사람 h가 있고 송아지 c가 좌표 위 일직선상에 존재한다
h는 1, -1, 5밖에 이동을 하지 못한다
이때 c에 도달하는 최단거리는?

s는 c보다 작고 s와 c는 1이상 10000이하이다

풀이과정

만약 h가 5, c가 14일때

1. 처음 h에서 시작해 무조건 1, -1, 5를 갈 수 밖에 없다
2. 하지만 여기서 dfs를 사용을 하면 운좋게 맞추면 아주 빠르게 맞추겠지만 아닐경우 개오래걸린다
3. 그렇기때문에 bfs를 사용한다
4. 먼저 각 레벨에 따른 트리를 그려본다
5. 
6. 위의 트리처럼 3레벨에서 14를 찾을 수 있다
7. 5를 큐에 넣고 큐의 사이즈만큼 반복문을 돌린다
8. 그리고 그 안에서 현재 값은 poll하고 1, -1, 5를 더한 값들을 큐에 넣는다
9. 레벨을 증가시키고 다시 큐의 사이즈만큼 반복한다
10. 이렇게 하다가 c와 같은 수가 나오면 레벨을 리턴한다
11. 하지만 시간복잡도가 너무 많아지기때문에 hashSet을 이용해 중복을 제거해준다 왜냐하면 위에 사진에서 보이듯이 레벨3에 있는 5는 이미 레벨이 3이지만 처음 시작과 같기때문에 최단경로에서 벗어났기때문이다
12. 그리고 마이너스로 간 경우도 제외시키고 10000을 넘어간 경우도 제외시킨다
13. 이렇게 되면 완성이다

코드

public class FindCalf {
    //송아지 찾기 bfs
    
    static int bfs(int h, int c) {
        int[] arr = {1,-1,5};
        HashSet<Integer> check = new HashSet<>(); //한번 넣은 수는 안넣게 하는 체크 배열

        Queue<Integer> q = new LinkedList<>();
        q.offer(h);
        int l = 0;

        while (!q.isEmpty()) {
            int length = q.size();
            for(int i=0; i<length; i++) {
                int num = q.poll();
                if(c == num) return l;
                for(int x : arr) {
                    int nx = num + x;
                    if(nx >= 1 && nx <= 10000 &&  !check.contains(nx)) {
                        check.add(nx);
                        q.offer(nx);
                    }
                }
            }
            l++;
        }

        return l;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int human = sc.nextInt();
        int calf = sc.nextInt();

        System.out.println(bfs(human,calf));
    }
}

Keep

dfs와 bfs중 시간복잡도가 적을 가능성이 높은것을 생각하는 사고

Problem

bfs구현에서 시간복잡도를 줄이기위한 if문처리 실패 (hash를 이용한 중복제거)

Try

항상 시간복잡도를 최선으로 줄이기를 노력하기
dfs, bfs둘 다 생각해보기