[일반] bfs에서 시작 지점 방문 처리 안해도 되지 않아?

[익명(tlazhddl)]

a에서 b까지 가는 최단시간 찾는 문제임

이 경우 곧장 다시 a를 방문하게 되어도

이미 최단시간도 아니고

a에 연결된 다음 노드들은 모두 방문처리 되어있어서 갈데도 없고

미미한 시간손해 제외하고는 상관 없지않아?

근데 어떤 문제 풀다가 시작지점 방문처리 여부로 정답 오답이 갈리더라

이유가 뭔지 모르겠어...

[익명(61.255)]

문제랑 코드를 봐야할 듯

[익명(tlazhddl)]

문제 저게 다임 bfs기초

[익명(61.74)]

답이 갈리는 문제를 그래프 그려서 확인 ㄱㄱ

[익명(tlazhddl)]

아 존나게 상관있었네 ㅋㅋㅋㅋㅋ visited[next] = visited[current] + 1로 최단시간 찾는거라 첫번째 방문이 제자리 방문이면 두번째 방문하기도 전에 visited[current] 값이 손상되네

[익명(110.76)]

제자리 방문을 왜함

[익명(222.109)]

https://www.acmicpc.net/board/view/130940
구현마다 다를 수 있는데, 이런 문제는 조금 패턴을 외워두는 것도 좋음

[익명(tlazhddl)]

그래프에 도돌이 간선도 있더라

[익명(14.37)]

상황마다 다름 한칸씩 이동하는 문제도 있는 반면 두칸씩 이동하기도함