-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
visited 체크 시점 질문있습니다!
21.06.07 16:25 작성 조회수 306
1
bfs에서는 우선 탐색을 하다가 해당부분이 true가 아니면(continue) true 체크를 하는데
dfs에서는 방문시점에 바로 visited true로 체크를하는데
이와같이 true로 방문 체크를 하는 시점이 다른 이유가 뭘까요?
답변을 작성해보세요.
1
푸샵맨 코딩스터디
지식공유자2021.06.07
yeahajeong 님 안녕하세요~
질문 감사합니다.
질문주신 내용: true로 방문 체크를 하는 시점이 다른 이유가 뭘까요?
=> 우리가 bfs, dfs를 푸는 방법선택은, 큐냐 스택이냐 입니다.
bfs는 큐를 dfs는 스택을 사용합니다. 그럼 그선에 처리하면 됩니다.
아래 내용을 잘 생각해보시면 될겁니다.
1. 먼저, dfs는 에러체크를 통과 즉시 파고 들기를 시작합니다.
dfs()를 재호출 하는 시점 전 이겠죠
public void dfs(){
에러 체크();
visited[] = true; //dfs()를 재호출 하는 시점 바로 전 이겠죠
dfs()
}
2. 그럼 bfs는 큐에 넣기 전이 만족하는 상황이므로 그때 visited에 true를 넣어주면 되겠죠?
public void bfs(){
visited[] = true; //큐에넣기 시점 바로 전 이겠죠
queue.offer()
}
지금 문제 업데이트 중에 있습니다.
이문제부터 업데이트 할게요~
업데이트되면 바로 댓글 올리겠습니다.(내일중으로 올립니다)
감사합니다~
답변 1