3-E 뮤탈리스크문제 질문있습니다

작성한 질문수 16

0

안녕하세요 선용님 ㅎㅎ

여기서 궁금한부분이 bfs일경우일때 visited[][][]3차원 배열에 이미 들어가있는 값이 있으면 continue하는 조건인데 q에들어가는 원소가 추후에 들어오는 visited일 경우 같은 원소의 idx라고 하여도 dfs가 아닌 bfs인 이상 무조건 count되는 레벨의 갯수가 트리나 그래프로 따졌을때 depth 가 깊은 탐색순서가 되기때문에

>> 아니요 bfs는 깊이우선탐색되지 않습니다.

visited가 원소가 있을때 이후에 들어오는 count는 무조건 기존에들어가있는 vistied의 원소보다 클 것이므로 해당조건만으로 문제를 풀수있는것인가요?

>> 네 맞습니다. 일단 visited에는 최단거리 배열만 들어가게 되며 먼저 채워지면 그 다음, 해당 visitied를 한 이후의 정점에서 채워지는 원소는 더 큰값이 들어오게 됩니다.

이렇게 탐색을 하기 때문에 먼저 방문한 정점이 최단거리이고 뻗어나갈수록 더 커진 값이 들어가게 됩니다.

			if (visited[na][nb][nc])
				continue;

또한 이 continue부분은 방문한 정점은 다시 방문하지 않는다라는 의미로 BFS라면 그냥 있는 로직입니다. 3차원이라고 해서 달라지지는 않습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.