쉽지 않은 bfs 문제였다. 일반적인 bfs 방식으로 풀면 메모리초과가 나는 것은 물론이고, 내가 처음에 풀었던 방식으로는 정답조차 나오지 않았다. 일반적인 bfs 같은 경우 그 때 그 때 마다 최선의 경우를 찾아서 큐에 넣는 방식인데 이 문제의 경우 현재 최선의 경우가 아니더라도 이후에는 최선의 경우가 될 수 있기 때문에 일반적인 bfs로는 풀 수 없었다. 아예 문제를 푸는 방식을 바꿔야만 했다. 문제의 알고리즘 분류를 보면 '이분 탐색' 이 있다. 그래서 이분 탐색을 이용해서 풀어야겠다고 생각했다. 그럼 어떤 것을 대상으로 이분 탐색을 진행해야 할까? 바로 (최대 - 최소)에 대해서 이분 탐색을 진행하면 된다. 우리는 경로를 구하거나 경우의 수를 구하는 것이 아니라 (최대 - 최소)의 경로가 하나라도..

꽤나 어려운 구현 문제였다. 처음엔 문제 이해하는 것도 쉽지않았다. 동굴이라고 해서 3차원 배열이 주어질 줄 알았는데 2차원 배열이 주어져서 '이게 어떻게 동굴인거지???' 하면서 삽질하다가 동굴의 단면임을 뒤늦게 알아차렸다. 그나마 다행인 것은 문제에서 입력으로는 공중에 있는 클러스터는 주어지지 않는다고 나와있었고, 클러스터가 떨어질 때 하나의 클러스터만 떨어진다고 가정한다고 되어있다는 점이었다. 이 덕분에 미네랄을 부수면서 공중에 있는 클러스터가 있는지 확인하고, 있다면 해당 클러스터를 떨어뜨리기만 하면 됐다. 미네랄을 부수는 것은 굉장히 쉬운 부분이므로 생략하고, 미네랄을 부순 후, 공중에 있는 클러스터를 떨어뜨리는 부분을 설명하겠다. 우선 공중에 있는지 확인하는 방법은 단순하게 바닥에 있는 미네랄..

기본적인 BFS 문제였지만... '골드바흐의 추측' 문제와 더불어 재채점 후 틀리게 된 문제다. 이 문제의 경우 메모리 초과가 발생하여 틀리게 되었다. 7개월 전에 풀었던 문제라 다시 내 코드를 분석했고, 왜 메모리 초과가 나오는지는 이해했다. 위의 사진이 메모리 초과를 발생시키는 입력예제이다. (예제 출처 : https://www.acmicpc.net/board/view/109356) 동일한 지점까지 같은 거울의 개수로 갈 수 있는 경우의 수가 여러 개 존재할 경우 메모리 초과가 발생할 수 있고, 위의 예제의 경우 메모리 초과가 발생하기에 충분한 경우의 수들이 존재한다. 그래서 처음에 거울의 개수를 같다면 거리가 더 짧거나 같은 경우만 선택해서 큐에 넣어주는 방식으로 코드를 수정했다. 그런데 이것도 메..