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

기초적인 것을 잊고 코드를 짰었네요...

다시 상기시켜주셔서 감사합니다 큰돌님 :)

안녕하세요 자르트님 ㅎㅎ

이부분이죠?

        for(int next : {here + 1, here - 1, here * 2}){
            if(next >= max_n || next < 0 || visited[next]) continue;  
            visited[next] = visited[here] + 1; 
            prev[next] = here; 
            q.push(next); 
        } 

TRACE하는 방식에서 헤매다가 큰돌님의 코드를 봤습니다! 그런데 만약 prev[next] = now 부분에

최단거리가 아닌 경우의 값이 now에 들어가게되면 이 값들을 tracing 할 경우 최단거리가 아닌 경우의 값을 tracing 하는 것 같은데 어째서 prev[next] 쪽의 코드가 최단거리인 경우의 prev 값만 저장하는 것인지 알 수 있을까요??

>> 지금 보시면 이렇게 방문한 지점은 방문하지 않습니다. BFS에서 최단거리만을 먼저 방문하는 것은 자명하니까요.

if(next >= max_n || next < 0 || visited[next]) continue;  

최단거리 값의 정답이 4인 문제라고 가정할 때

제가 bfs를 돌렸을 때 최단거리 값이 6이나온 상태에서 here == k 라는 while문의 기저 사례 코드를 만나 종료가 됐다고 가정하면, prev[목적지]에 저장된 값들을 tracing 하면 4인 정답의 경로를 trace 하는 게 아니라 6인 정답의 경로를 trace하는 것 같아서 질문 드립니다!

>> 아뇨 그럴일은 없습니다.BFS에서는 먼저 방문한 지점은 최단거리입니다.

그림을 그려볼까요?

이처럼 BFS로 방문할 때 visited를 걸게 되는데 먼저 방문한 지점이 최단거리임은 자명합니다.

감사합니다.