3-e 질문드립니다

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요! 시간복잡도 관련한 질문입니다. 모든 경우를 생각했을 때 (60,60,60) 에서 계속 (9,3,1)을 빼는게 최악이라 생각했고 이 경우까지 도달하기 위해선 1+6+6^2+..6^60 이라 생각해서 그래프로 풀 생각을 하지 못했습니다. 그런데 강의에선 bfs로 최단거리를 구했더군요. 최악의 경우에 도달하기 전에 0,0,0이 되는 순간이 존재하니 가능한 풀이인가요? 아니면 제가 최단거리 개념에 대해 잘못 알고 있는걸까요? 감사합니다.

큰돌 · Answer

안녕하세요 ㅎㅎ 모든 경우를 생각했을 때 (60,60,60) 에서 계속 (9,3,1)을 빼는게 최악이라 생각했고 이 경우까지 도달하기 위해선 1+6+6^2+..6^60 이라 생각해서 그래프로 풀 생각을 하지 못했습니다. -> 처음에 시간복잡도 판단은 좋았는데요. ㅎㅎ BFS로 풀게 되면 반복되는 경우의 수를 visited로 걸러내고 해당 부분부터 시작되는 경우의 수가 감소하기 때문에 풀 수 있다고 생각하시면 됩니다. 예를 들어 어쩌다 보니 30, 30, 30 까지 오는 경우의 수가 10개가 존재한다라고 하면 그 다음부터 최대는 10* 6 ... 이런식으로 가게 됩니다. (만약 방문처리를 안하면요.) 하지만 bfs - visited로 방문처리를 하기 때문에 해당 경우의 수는 1개만 존재하게 되어 계산해야 하는 경우의 수가 줄어들게 됩니다. 어차피 우리가 원하는 것은 최솟값인데 예를 들어 해당 경우의 수를 12, 15, 9번만에 방문했을 때 필요한 것은 9번부터 시작되는 경우의 수임이 자명합니다. 만약 각각 9, 9, 9번만에 방문하더라도 방문처리가 되어있으면 이 중 단 한번만 체크하면 되기 때문에 그 이후로부터 경우의 수가 기하급수적으로 증가하지 않게 되는 효과가 있는 것이죠. 이러한 부분들을 생각해서 bfs로 접근하면 되지 않을까? 하고 들어가시면 됩니다. 감사합니다.