skysujun   3달 전

bfs로 갈수 있는 노드에 방문하고, 나름 메모이제이션도 사용했다고 생각하는데 계속 틀렸다고 나옵니다. 혹시 문제가 뭔지 아시는 분 계신가요?

로직 상의 문제는 없어 보이나, 두 가지 문제점이 있습니다.

첫 번째는 queue의 크기가 부족합니다. 배열은 25만칸이지만,

예를 들어

1 4

2 3

과 같은 2*2 보드에서, 1행 2열의 4는 (1,1)->(2,1)->(2,2)->(1,2)에서 한 번, (1,1)->(1,2)에서 한 번 총 2번 푸시됩니다.

이렇게 되면 (2,1)에서 갈 수 있는 모든 칸은 두 번씩 방문되겠네요.

이 과정이 여러 번 중첩해서 쌓이면 100만 칸을 넘어갈 수 있습니다.


방문 체크를 통해 이 부분을 개선할 경우엔 두 번째 문제점이 있습니다.

현재 코드는 사실 DP가 아닙니다. 중복 계산되는 문제를 여러 번 중복 계산하는 것을 허용하고 있기 때문입니다.

N*N개의 칸에 대해 BFS를 실행하게 되니 시간복잡도는 O(N^4)이 되고, 만일 충분히 악의적인 입력이 있다면 시간 초과가 나겠네요.

이 문제는 (r,c)에서 시작하는 최대 경로 길이를 이용하는 O(N^2) DP 풀이가 존재합니다. 한번 다시 설계해보세요.

댓글을 작성하려면 로그인해야 합니다.