porrshe   2년 전

음 일단 ㅜㅜdfs를 처음들어가게됬어요.

미로탐색문제를 dfs로 푸는데 70%까지 올라가더니 틀렸습니다 나오더라구요,,

그후로 미로탐색필독게시판읽었습니당.

그래도 궁금해요 제소스틀린부분을 고쳐도 마지막엔 시간초과가 뜰까요?

제 소스가 dfs방식이 맞는지 궁금합니다.또 혹시 여기서 고칠 수 있다면 어떻게 고쳐야 할지 알 수 있을까요?

  1. 최저값을뽑기위해 check배열방에 987을 넣음
  2. dfs돌림 ->가려는 길이 '1'이면 상하좌우로 뻗어나감
  3. 최소값을 뽑기위해 check[y][x]>cnt일때만 들어감

jh05013   2년 전

70%나 올라간다는 것도 신기하군요. 정답이 최대 얼마까지 갈 수 있는지 생각해 보세요.

그리고 FAQ 글을 읽으셨다면 알겠지만, 최단거리 문제는 절대로 DFS로 풀면 안 됩니다. check[y][x]>cnt일 때만 DFS를 진행하면 적어도 이 문제는 풀 수 있지만, BFS보다 훨씬 비효율적이고 입력의 크기가 조금이라도 더 커지면 시간 초과가 납니다.

porrshe   2년 전

앗 감사합니다!!

제가 알고리즘시간복잡도를 계산하려고 인터넷검색도해보고 하는데 실제문제에 적용시키려고 하면 감이안잡혀요ㅜㅜ

다양한 알고리즘을 공부하는게 답일까요? 그 시간복잡도를 좌우하는 기준을 잘 못잡겠어요(for문이나 진짜 간단한거 빼고!)예를 들면 dfs나 bfs..?

이걸로 뭘 하느냐에 따라서 시간이 달라지는 건 알겠는 데 어렵네요ㅜㅜ

혹시 시간나시면 조언해주실 수 있을까요..!

porrshe   2년 전

일단 제가 틀린부분을 찾아서 수정해서 성공은 시켰습니다!

jh05013   2년 전

사용된 알고리즘의 시간복잡도를 알고 있으면 그 복잡도 식에서 사용된 변수의 값을 대입해서 알 수 있습니다. 예를 들어 BFS같은 경우 한 번 방문한 정점을 다시 방문하지 않기 때문에, 정점과 간선의 개수로 시간 복잡도를 결정할 수 있습니다. 그 개수가 얼마인지 문제에서 알아내는 것은 물론 푸는 사람의 몫입니다.

porrshe   2년 전

wow 명확해졌어요! 두 분 정말 감사합니다!!

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