queue 1

문제는 더블릿 14 queue에 있는 catch_cow입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/catch_cow/catch_cow.php?pname=catch_cow

수 N과 K가 주어지고 N을 *2, +1, -1을 한번 할 때마다 카운터가 증가합니다.  이 때 N이 K가 될 수 있는 가장 적은 경로(카운터 크기)를 구하면 됩니다.

친절하게 queue로 풀으라고 알려주고 있으니 그렇게 만듭니다.  기본적으로 리스트에 어떤 경우의 값을 다 넣어주고 반복이 진행되면서 그 값들을 전부 빼서 검사를 진행합니다.  그리고 그 결과 답이 나오지 않으면 다음 경우의 수들을 다시 리스트에 전부 넣어주고 검사하는 것을 반복합니다.

먼저 첫 N값을 리스트에 넣습니다.

그리고 bfs를 실행할 while문에 들어갑니다.

리스트에 들어있는 값을 꺼내봤을 때 K이면 종료하는 조건을 줍니다.

종료 조건에 만족하지 않은 경우 검사한 값은 빼고 다음 값들을 넣어줍니다.

여기서는 N값에서 *2, +1, -1한 값을 리스트에 넣어줄 겁니다.  그런데 항상 이렇게 넣어주기만 할 경우 숫자가 커지면 시간 초과 에러가 발생합니다.

조건을 더 추가해서 리스트에 넣어주는 수들을 줄여야 합니다.  

값들을 나열해보면 중복되는 값이 들어가는 것을 알 수 있습니다.  저는 map을 생성해서 이 맵에 리스트에 넣어준 값을 넣어주었습니다.  그리고 리스트에 넣어주기전에 map을 검사해서 이 값이 이전에 리스트에 넣어준 값이면 넣어주지 않도록하였습니다.

이렇게 해도 시간 초과가 뜨는데 리스트의 값을 보면 넣어주지 않은 값이지만 N과 K의 값에서 한참 떨어져있는 값들이 들어가 있는 것을 확인할 수 있습니다.

테스트 케이스로도 있는 1000 8888의 경우 리스트에 8384829와 같은 값이 들어 가 있을 수 도있습니다.  그렇기 때문에 리스트에 들어갈 수 있는 값의 크기를 제한해줘야 합니다.  

저는 리스트에 들어갈 수 있는 값을 K+(N*2)보다 작거나 같을 경우에 넣어주도록 하였습니다.

K*2로 해도 시간 초과 에러가 뜨지만 위와 같은 경우 너무 범위를 넘지 않도록 하면서 문제의 테스트 케이스에 나오는 웬만한 경우의 수들을 테스트하여 accept를 받을 수 있습니다.