C++_12주차_정리

BFS : 너비우선탐색

DFS : 깊이우선탐색

 

[게임 구조 설명]

# :벽을 의미

E :적

P :플레이어

 

bfs_map[][]

 

step1)

 

0 1 2 3 4 5 6 : X

0 # # #

1 # # # #

2 # # P

3 # E #

4 # #

5 # #

6 # #

Y

X, Y

E 적 위치 = (2, 3)

P 내 위치 = (4, 2)

 

step 2) 부모 인덱스 번호 = -1 (초기값)

 

step 3)

bfs_list --> [0] (2, 3, -1) //적의 위치를 시작 위치로 [0]

0 1 2 3 4 5 6 : X

0 # # #

1 # # # #

2 # # P

3 # [0] #

4 # #

5 # #

6 # #

bfs_list ---> [0] (2, 3, -1) //적 E 위치

(0)기준 -> [1] (2, 2, 0) // 상 -> [2] (2, 4, 0) // 하 -> [3] (1, 3, 0) // 좌 .

<우 = 벽이라 이동 불가>

 

bfs_list --> [0] (2, 3, -1) //적의 위치를 시작 위치로 [0]

0 1 2 3 4 5 6 : X

0 # # #

1 # # # #

2 # [1] # P

3 # [3] [0] #

4 # [2] #

5 # #

6 # #

 

step 4)

bfs_list -->[0] (2, 3, -1) //적 E 위치

-> [1] (2, 2, 0) //[0]의 상 -> [2] (2, 4, 0) // 하 -> [3] (1, 3, 0) // 좌 .

-> [4] (2, 1, 1) //[1]의 상 -> [5] (1, 2, 1) //[1]의 좌

 

0 1 2 3 4 5 6 : X

0 # # #

1 # # [4] # #

2 # [5] [1] # P

3 # [3] [0] #

4 # [7] [2] #

5 # [6] #

6 # #

 

이제 [2]기준

bfs_list -->[0] (2, 3, -1) //적 E 위치

-> [1] (2, 2, 0) //[0]의 상 -> [2] (2, 4, 0) // 하 -> [3] (1, 3, 0) // 좌 .

-> [4] (2, 1, 1) //[1]의 상 -> [5] (1, 2, 1) //[1]의 좌

-> [6] (2, 5, 2) //[2]의 하 -> [7] (1, 4, 2) //[2]의 좌