3-G 질문있습니다.

안녕하세요 은정님 ㅎㅎ

일단은 이 문제는 최단거리를 구하는 문제 + 경우의 수를 구하는 문제입니다.

이를 처음에 재귀 - dfs로 하는 생각자체는 괜찮습니다.

경우의 수는 모름지기 그렇게 재귀로 +해가면서 해야하거든요 ㅎㅎ

다만.. 이렇게 되면 최단거리를 구할 수는 있으나 너무나도 많은 시간이 걸리게 됩니다.

예를 들어

파랑색 정점을 통해 최단거리를 구했는데도.

다시 빨간생 정점들을 다시 탐색해야 합니다.

    if (s == e)
    {
        if(mnMove == cnt)
            mnCnt++;
        mnMove = min(cnt, mnMove); // 도착점에 도착했을 때 이동 횟수를 갱신
                          // 도착점에 도착한 경우 카운트
        return mnMove-1;             // 이동 횟수 반환
    }

도착 지점에서 mnMove 값 생성

그 후.

        cnt++;                       // 이동 횟수 증가
        int ret = solve(ns, e);      // 재귀 호출
        minMove = min(ret, minMove); // 현재 위치에서의 최소 이동 횟수 갱신
        cnt--;

다시 탐색해 나가면서 minmove인지를 확인.

이렇게 다시 탐색해나가는 것이죠.

이 때문에 시간초과가 뜨는 것 같습니다.

참고 :

그러나 최단거리를 탐색하는 것은 무조건 깊이우선이 느릴까요?

이 경우는. 느립니다.

만약 bfs로 하게 되면 2번만에 찾을 것을 dfs는 여러번 탐색하게 되는 것이죠. 그러나 만약 저 파랑 정점 끝이 답이라면? bfs가 더 효율적이지 않게 됩니다.

참고 삼아 알아두시면 좋습니다. ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변