hazxz   1달 전

처음에는 다이나믹으로 풀려고 했습니다 ( DFS)

하지만 틀린 경우가 나와 밑에 문제 분류를 보니 BFS라서 BFS로 제출하니 맞았습니다가 뜨네요

DP[x][y][cnt] = x,y위치에서 k가 cnt만큼 남았을때 최소의 움직임 로 정의했습니다.

이런 방식이 DFS로 탐색을 하게 될텐데

누군가가 "먼저" 도착하게 되는 경우 그곳의 값이 최적이 아니게 되는 경우가 발생하는게 DFS인거 같은데

DP 정의를 저런식으로 해두면 각각의 위치에서 최적해를 가지게 되지 않나요?

어떤 차이가 있는지 궁금합니다.

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