3-H

Question

TRACE하는 방식에서 헤매다가 큰돌님의 코드를 봤습니다! 그런데 만약 prev[next] = now 부분에 최단거리가 아닌 경우의 값이 now에 들어가게되면 이 값들을 tracing 할 경우 최단거리가 아닌 경우의 값을 tracing 하는 것 같은데 어째서 prev[next] 쪽의 코드가 최단거리인 경우의 prev 값만 저장하는 것인지 알 수 있을까요?? 최단거리 값의 정답이 4인 문제라고 가정할 때 제가 bfs를 돌렸을 때 최단거리 값이 6이나온 상태에서 here == k 라는 while문의 기저 사례 코드를 만나 종료가 됐다고 가정하면, prev[목적지]에 저장된 값들을 tracing 하면 4인 정답의 경로를 trace 하는 게 아니라 6인 정답의 경로를 trace하는 것 같아서 질문 드립니다!

자르트 · Answer

기초적인 것을 잊고 코드를 짰었네요... 다시 상기시켜주셔서 감사합니다 큰돌님 :)

큰돌 · Answer

안녕하세요 자르트님 ㅎㅎ 이부분이죠? 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를 걸게 되는데 먼저 방문한 지점이 최단거리임은 자명합니다. 감사합니다.