daye19415   3년 전

예제는 맞게 나오는데 자꾸 틀렸다고 결과나오네요.

다른 예제로도 풀어봤는데 맞는거 같은데 어디서 틀린건지 잘모르겠어요

알려주시면 감사하겠습니다!

ljh6274   3년 전

bfs가 아닌 dfs로 탐색을 하셨네요

bfs였다면 위와같은식으로 하시면 아마 맞는 풀이법이 되었을텐데요, 스택을 사용한 dfs의 경우 먼저 방문을 한 정점이 나중에 방문할때보다 더 비용이 클 수 있습니다. 무슨 얘기냐면

만약 1 2, 1 3, 2 3, 3 4, 2 4, 2 5, 4 5  이런 경우를 생각해 보죠

그러면 정점 1에서 dfs를 통해 탐색을 하면 처음 

pop 1 / 스택 - 2(1), 3(1) / top(3)

pop 3 / 스택 - 2(1), 4(2) / top(4)

pop 4/ 스택 - 2(1), 5(3) / top(5)

이러한 순서로 돌게 됩니다. 정점 옆의 괄호는 visited변수에 저장될 값입니다.

이로 인해 1->5는 3이라는 값이 저장되어 더 이상 변하지 않을것 입니다.

하지만 실제로는 1->(2, 3)->(4, 5)로 2라는 값이 저장되어야 하는거죠

그래서 스택을 돌면서 처음 도착한 정점이거나 아니면 이전에 저장된 값 보다 빠른 이동으로 왔을 경우 값을 갱신하여 주어야 합니다.

질문자님께서 작성하진 코드에서 if문을 약간 수정하면 되는데요, 스택에 도는 while문 내의 조건문을 아래와 같이 수정하시면 될것 같습니다.

if(friend[index][j]==1 && (visited[i][j]==0 || visited[i][j]>visited[i][index]+1)&& j!=i)

daye19415   3년 전

아 감사합니다 그 경우를 생각하지 못했네요

설명 너무 잘해주셔서 바로 이해가 되었네요 !! ㅎㅎ

돌려보니까 잘 돌아가네요

감사합니다!!!

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