스택의 활용 예시
깊이 우선 탐색(DFS)과 너비 우선 탐색의 구조
깊이우선탐색(DFS)과 스택
A를 검사해서 D,C,B를 담아둠, 
B를 검사해서 D,C,F,E 를 담아줌
=> 정답이 없음, E는 검사 종료
E를 검사해서, D,C,F,J를 담아줌,
=> 정답이 없음, J는 검사 종료
J를 검사
깊이우선탐색 구현 : 미로찾기
주어진 미로가 탈출가능한 미로라면 True, 아니라면 False 반환
(0.0)부터 검사시작 => 이동가능한 좌표 (0,1)을 stack에 담아둠 (0,0)검사종료
-> (0,1) 검사시작(도착이 아니므로 가능한 좌표를 stack에 담아둠),
->(1,1)(0,2)를 stack에 담아둠 stack위에 담긴 (0,2)검사
-> 이동가능한 (0,3)좌표를 담고 검사종료 ->(0,3)검사중-> 이동가능한 (0,4)를 담고 검사종료... 정답을 찾을수없음
->아까 담아두었던 (1,1) 남아있음 -> 반복
python
while len(stack)>0:
now=stack.pop() #스택의 가장 마지막 데이터 추출
if now==dest: #정답여부검사
return True
x=now[1]
y=now[0]
if x-1 > -1: #x축의 왼쪽으로 이동할 수 있다면(인덱스값을 벗어나지않기위해 -1)
if maps[y][x-1]==0:
stack.append([y,x-1]) #스택에 추가
maps[y][x-1]=2 #방문여부를 2로표시
if x + 1 < hori: #x축의 오른쪽으로 이동할 수 있다면(인덱스 맵크기 벗어나지x)
if maps[y][x+1]==1:
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 #스택에 데이터가 없으면 False너비우선 탐색의 구조
: 같은 레벨의 단계를 모두 검사하고, 아니면 다음 레벨을 탐색
너비우선 탐색과 큐
=> Q는 선입선출의 구조로 B부터 검사
E,F를 담아두고 검사종료 , C검사, 정답 담아주고 종료 (C는 정답아니기에),
D검사, D정답 아니기에 H,I를 담아두고 검사종료,
....
너비우선탐색(BFS) 구현: 최단경로 찾기
섬과 섬과의 거리와 이것의 개수를 구할 변수가 주어져야함.,
섬1의 스택을 넣었을때
거리 0의 개수=1 (1번섬-1번섬과의 거리:1개)
섬1의 스택이 검사중일때
거리 0의 개수=0
(다음에 들어올 데이터들은 거리가 1인 섬)
2, 5, 6을 스택에 담음
거리 1의 개수=3
2번섬 검사중
거리 1의 개수=2
2번섬과 연결된 3,11을 스택에 담아둠
2번섬 정답 아니므로 종료
5번 검사중
거리1의 개수=1 (6번섬)
5번섬과 연결된 9,11 담아줌(11번 있으므로 9번만)
6번검사중
거리 1의 개수=0
6번섬과 연결된 3,12 담아줌(3번 있으므로 12번만)
거리2의 개수=4개
....
python
while len(queue)>0: #큐에 데이터가 있다면
count = len(queue) #같은거리에 있는 큐 데이터 갯수
for time in range(count): #같은 거리에 있는 큐 개수만큼 검사
now=queue.pop(0)
if now == dest: #정답이 존재하면 값 반환
return answer
for i in data: #연결된 포인트 완전탐색
if i[0]==now and visited[i[1]-1]==False: #방문하지 않은 연결된 길이라면 큐에 추가하고 방문표시
queue.append(i[1])
visited[i[1]-1]=True
elif i[1]==now and visited[i[0]-1] ==False:
queue.append(i[0])
visited[i[0]-1]=True
answer+=1 #거리를 1 더 벌린다.
return answer