[알고리즘]STEP 1-3주차 BFS/DFS(내용정리)

✅ 깊이우선탐색(DFS)

Depth First Search. 하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정

구조

A에서 시작. B->E->J 순서로 탐색 F->K 순서로 탐색 L 탐색 C->G->정답 순서로 탐색. 알고리즘 종료

스택의 활용

A부터 탐색 시작. A는 정답이 아니므로 A의 자식노드 B,C,D 스택에 입력

스택의 제일 마지막 노드 B 탐색. B는 정답이 아니므로 B의 자식노드 E,F 스택에 입력

스택의 제일 마지막 노드 E 탐색. E는 정답이 아니므로 B의 자식노드 J스택에 입력

ex) 미로찾기

✍🏻 깊이우선탐색 구현

while len(stack)>0:
	now =stack.pop()
	if now==dest:
    	return True
    x=now[1]
    y=now[0]
    if x-1>-1: #왼쪽으로 이동할 수 있다면
    	if maps[y][x-1]==1: #갈 수 있는 길이라면 스택에 추가하고 방문여부를 2로 표시
        	stack.append([y,x-1])
            maps[y][x-2]=2
    if x+1<hori: #오른쪽으로 이동할 수 있다면
    	if maps[y][x+1]==1: #갈 수 있는 길이라면 스택에 추가하고 방문여부를 2로 표시
        	stack.append([y,x+1])
            maps[y][x+1]=2
    if y-1>-1: #위로 이동할 수 있다면 
    	if maps[y-1][x]==1:
        	stack.append([y-1,x])
            maps[y-1][x]==2
    if y+1<verti: #아래로 이동할 수 있다면
    	if maps[y+1][x]==1:
           	stack.append(y+1,x])
            maps[y+1][x]=2
return False  
          

✅ 너비우선탐색

Breadth First Search. 하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정

너비우선탐색 구조

A에서 시작 B->C->D 탐색 E->F->정답 탐색. 알고리즘 종료

큐의 활용

A에서 시작. 정답이 아니면 A의 자식노드인B,C,D 큐에 입력
큐의 첫번째 노드인 B 탐색. 정답이 아니면 B의 자식 노드인 E,F 큐에 입력
큐의 첫 번째 노드인 C 탐색. 정답이 아니면 C의 자식 노드인 정답 노드 큐에 입력
큐의 첫 번째 노드 D 탐색. 정답이 아니면 D의 자식 노드 H, I 큐에 입력
큐의 첫번째 노드 E 탐색. 정답이 아니면 E의 자식 노드 J 큐에 입력
큐의 첫 번째 노드 F 탐색. 정답이 아니면 F의 자식 노드 K, L 큐에 입력

큐의 첫 번째 노드 정답 노드 탐색. 알고리즘 종료

✍🏻 너비우선탐색 구현