맹목적인 탐색 잘 모르겠어요....

Question

이 그림의 너비 우선 탐색 순서가 어떻게 되나요?????????????????? 잘 모르겠어요........................

Answer 1

안녕하세요. 김민규 전문가입니다.

아래와 같이 탐색 순서를 하게 되시면 최단 경로로 이동이 가능하오니 참고하시기 바랍니다.

A -> B -> H -> M -> N -> O -> T -> X

Answer 2

안녕하세요. 조일현 전문가입니다.

사진상 이동 가능한 방향은 나와 있지 않지만 일반적으로 상하좌우로 인접한 칸으로 이동할 수 있다는 가정하에

A -> B -> K -> C -> L -> P -> H -> M -> V -> U -> N -> W -> Y -> O -> X 입니다.

위 순서는 상하좌우 이동이 가능하고 회색 칸이 막혀 있다는 가정하에 결과 입니다.

Answer 3

안녕하세요. 서종현 전문가입니다.

너비 우선 탐색(BFS) 순서는 주어진 상태에서 인접한 노드를 계측적으로 탐색하는 방법입니다. 주어진 그림에서 너비 우선 탐색을 진행하면 다음과 같은 순서로 탐색됩니다.

1. A(시작상태)

2. B,C,H,K,L,M,N,O(A의 자식 노드들)

3. P,U,V,W(K의 자식 노드)

4. X(W의 자식 노드)

5. Y,Z(U의 자식 노드)

따라서, BFS탐색 순서는 다음과 같습니다.

A → B → C → H → K → L → M → N → O → P → U → V → W → X → Y → Z