너비 우선 탐색. 하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 많이 사용
A 검사 후 B,C,D 저장 -> B 검사 -> 정답이 아닐 경우 연결된 E,F 저장
1번 검사 후 연결된 2,5,6 저장 -> 2번 검사 후 3, 11 저장. 정답이 아닐 경우 거리 1의 개수 -1
while len(queue) > 0: # queue에 데이터가 있다면
count = len(queue) # 같은 거리에 있는 queue 데이터 개수
for time in range(count): # 같은 거리에 있는 queue 개수 만큼 검사
now = queue.pop(0)
if now == dest: # 정답이 존재하면 값 반환
return answer
for i in data: # 연결된 포인트 완전 탐색
if i[0] == now and visited[i[1] -1] == False: # 방문하지 않은 연결된 길이라면 queue에 추가하고 방문 표시
queue.append(i[1])
visited[i[1] -1] == True
elif i[1] == now and visited[i[0] -1] == False: # 방문하지 않은 연결된 길이라면 queue에 추가하고 방문 표시
queue.append(i[0])
visited[i[0] -1] == True
answer += 1 # 거리를 1 더 벌림
return answer
DFS (Depth First Search)
깊이 우선 탐색. 하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈수 없게 되면 다시 가장 가까운 갈림길로 돌아와 다른 방향으로 다시 탐색을 진행하는 방법과 유사 모든 노드를 방문 하고자 할 경우 많이 사용
A 검사 후 B,E,F 검사 -> 정답 아닐 경우 F,K,L 검사 -> C 검사 후 G, 정답 -> 종료
while len(stack) > 0: # stack에 데이터가 있는지 검색
now = stack.pop() # 데이터가 있다면 마지막 데이터 추출
if now == dest: # 정답 여부 검사
return True
x = now[1]
y = now[2]
if x -1 > -1: # 왼쪽으로 이동할 수 있다면
if maps[y][x-1] == 0: # 갈 수 있는 길일때 stack에 추가하고 방문여부를 2로 표시
stack.append([y, x-1])
maps[y][x-1] = 2
if x + 1 < hori: # 오른쪽으로 이동할 수 있다면
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
retrun False
