gyurious   2년 전

DFS로 짰는데 위의 코드는 맞고 아래 코드는 틀립니다...

다르게 한건 top-down이냐 bottom-up이냐 밖에 없는 것 같아요;;

심지어 함수 구성도 거의 같다 시피 한데 왜 위에껀 맞고 아래껀 틀리는지 모르겠습니다ㅠㅜㅜㅠ

머리가 안 돌아가는 저를 도와주세요 고수님들...!!!!

eric00513   2년 전

저도 두 소스 비슷해 보이는데, 죄송하지만, 아직 이유는 못 찾았어요 한 가지 질문 할게요

왜 INF를 1987654321로 정했을까요? 이유를 알고 싶어요

gyurious   2년 전

@eric00513

N,M이 100이므로 미로의 칸의 최대 개수가 10000개이므로, INF가 10000보다만 크면 될 것 같아서 그냥 1987654321로 설정했어요 !!

eric00513   2년 전

몰라서 여쭈어 본게 아니라 굳이 1987654321로 할 필요가 없을 것 같아서 여쭈어 본 거에요 INF는 최소한으로 잡는게 좋아요 (가능한 것 중) 왜냐하면 너무 막 잡다가 잘못하면 int범위를 넘어갈 수도 있어요.

gyurious   2년 전

@eric00513

앗 그렇군요!!

말씀듣고 INF를 198765로 재설정해봤는데 여전히 틀리네요...ㅠㅜㅜ

jh05013   2년 전

이게 통과된다니 데이터가 심각하게 약하군요. 둘 다 틀린 풀이입니다.

최단거리는 절대로 DFS로 찾을 수 없습니다.

eric00513   2년 전

하긴...전 그래프는 무조건 DFS로 풀고요 (BFS는 큐 써야 되고 귀찮아서) 최단거리는 수학적이나 동적 계획법으로 풉니다.

eric00513   2년 전

이건 그 전통식 최단거리 구하는 방법이 좋지 않을까요? 알고리즘 분류가 BFS이긴 한데...

gyurious   2년 전

@jh05013

앗, 절대 안되는군요....

n,m이 좀 작고 100*100을 모두 1로 채운 테스트도 통과하길래 될 줄 알았어요ㅠㅜ

sgy8971   2년 전

@jh05013

최단거리는 절대로 DFS로 찾을 수 없습니다.

이 댓글을 남기셨는데

1) 모든 최단 거리 문제는 DFS로 안된다는건가요?

2) 이 문제를 DFS로 하면 시간 초과가 뜨는데 그 이유를 알 수 있을까요?

아무래도 시간복잡도가 엄청날꺼 같은데...

DFS로 하게되면 시간복잡도가 어떻게 되나요 ㅠㅠ 

jh05013   2년 전

간단히 말해서 DFS는 가능한 모든 경로를 탐색합니다. 이 문제에서 아래쪽과 오른쪽으로만 갈 수 있다고 가정해도 경로의 개수는 2^100개를 넘으며, 왼쪽과 위쪽까지 허용하면 상황이 훨씬 심각해집니다. 이걸 막겠다고 방문 체크를 해 버리면 최단경로와는 아무 상관 없는 경로가 만들어집니다.

eric00513   2년 전

@jh05013님의 의견에 의하면, 2100=1267650600228229401496703205376이며, 1초에 100000000 (1억)개의 경로를 탐색한다고 하더라고 최소  12676506002282294014967초 정도 걸립니다. (수만년 이상이 걸리는군요^^;;)

eric00513   2년 전

@sgy8971

위 댓글을 보시면 시간 초과가 날 수 밖에 없다는 것을 알게 되실 것입니다.

sgy8971   2년 전

@jh05013 @eric00513

이해 됐습니다 감사합니다 !!!

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