cubalys   8달 전

0 0 -> N-1, N-1 

의 방으로 가는 모든 경우의 수 중 검은 방을 가장 조금 거쳐가는 경우의 수를 찾는 방식으로 작성했습니다.

재귀적으로 구성해

현재 방의 상태를 더해 return 하도록 하며

계속 최솟값을 갱신하도록 했습니다.

예제코드도 맞게 안나오는데..

어느부분에서 틀렸는지 감이 안오네요

아예 접근 방법이 잘못된건가요?

f52985   8달 전

5 5

11111

00001

11111

10000

11111


정답 : 0

출력 : 1


위 예제와 같이 구불구불 가는 것이 최소일 경우가 있기 때문에, 단순히 DFS로만 구현하면 정확한 답을 구할 수 없습니다.

cubalys   8달 전

DFS로 진행해도 모든 경우를 탐색 하지 않나요??

왼쪽 으로 진행하는 경우와 상단으로 진행하는경우도 모두 가기 때문에 

저 경우도 탐색할것이라고 생각했는데 아닌가요..?

f52985   8달 전

위의 코드가 배열을 탐색하는 방향을 보면,

아래, 위, 오른쪽, 왼쪽

순서로 탐색을 하게 됩니다.

그러면 MAP[0][0]를 시작으로 거쳐가는 검은 방의 수를 최소로 만드는 경로는 오른쪽으로 출발해서 MAP[2][0]을 거쳐가는 경로일텐데, 

MAP[2][0]은 이미 극초반에 한번 거쳐가므로 check[2][0]의 값은 1이 되고, 나중에 오른쪽으로 가는 경로가 MAP[2][0]을 거쳐가려고 할 때 그곳은 이미 체크되어있기 때문에, 최적의 경로를 갈 가능성 자체가 아예 존재하지 않게 됩니다.

(물론 실제로는 오른쪽으로 가는 경로 (즉 DP[0][1])을 구하려고 할때는, MAP[2][0]에 다가가기도 전에 이미 체크된 좌표를 밟고 탐색을 그만할 것입니다.)

cubalys   8달 전

DFS의 끝부분에 체크를 헤제해 주는데도 문제가 되나요?? 

아래로 갔다가 다시 0 0 으로 return 될때는 2 0 의 체크가 헤제되니 갈거라고 생각하고 짰습니다.

제가 이해를 잘못 하고 있는건가요?

DFS 자체는 모든 경로를 탐색하기때문에 최적경로를 언젠가는 찾을것이라고 생각되네요.

문제는 dp인데, 최적의 경로가 아닌길을 우선적으로 탐색을 마쳤을 경우 dp배열에 dp값이 기록이 됩니다.

그럼 그 다음 탐색시 dp값이 있기때문에 그 값을 바로 반환하게 되겠죠 그래서 문제가 생기는게 아닐까 싶습니다

cubalys   8달 전

아 그러네요 이해 했습니다 ㅋㅋ 감사합니다

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