[2292번] 백준 벌집 문제

문제 접근

초기 문제 접근

최단거리라 하여 BFS [ 넓이 우선 탐색 ]법을 이용해 접근했다. 출력 값에 오류는 없었으나, 메모리 초과로 에러가 발생하였다 ㅠㅠ
타인 문제 풀이

결국 4시간 만에 참조한 타인의 풀이를 보니 숫자의 범위를 풀이에 활용하더라! 세삼 똑똑하신 분들 너무 많다 ㅠㅠ

나의 풀이

우선 BFS로 접근해야 하기에, Queue 자료구조를 이용했다. [ 최소거리라 하여 무조건 범위 탐색으로 접근해야 한다고 생각했다 😅 ]

숫자를 담는 [ number_que ]와 각 number당 count 수를 담는 [ count_que ]와 해당 범위에 접근하는 증가값을 담은 [ increase_que ]를 활용했다.

무한반복문으로 접근하며 만약 찾고자 한 값과 number_que로 poll( )한 값이 동일하다면 count_que.poll( )한 값을 return하여 마무리했다.

매우 큰 문제는 코드가 길다. 길기도 하며, 접근 법에 대해 비효율적이라는 생각이 들었지만 생각의 전환이 어려웠다 😂

어떻게하면 효율화 할 수 있을지 검사하기 위해 반복문이 작동할 때마다 모든 값을 출력하였고, 일정 범위별로 count 값이 동일하다는 것을 발견했다.

하지만 이를 어떻게 활용할지는 접근하지 못했었다.

타인 풀이

접근법부터 다르셨다. 이분 풀이의 경우 값의 범위를 활용하셨다.

위 그림이 무슨 말이냐. 1부터 값이 증가하며 6배수의 단위로 겹겹이 벌집이 쌓이게 되며, 이동경로의 최솟값은 겹의 번호와 동일하다는 것이다. 그래서 해당 값의 범위를 활용해 접근하는 것이다.

마찬가지로 while문으로 무한루프를 돌며 만약 찾고자 하는 값보다 계산한 합이 더 크면 탈출하고 count 값을 return하는 것이다.

이는 다음 코드에서 살펴보자.

이중 answerCode.java를 확인하면 된다.

개선점

문제를 단순하게 접근하자..ㅠ 너무 꼬아서 생각하다보니 먼 길을 돌아 돌아 푼 느낌이 강하다. 규칙을 찾는 연습을 더 많이 하자.

규칙을 찾는다면 코드는 더욱 단순해진다!

하늘