깊이우선탐색(DFS)
- Depth First Search의 약자로 넓이 우선 탐색을 의미
- 하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정
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] == 0://갈 수 있는 길이라면
stack.append(y, x - 1)//스택에 추가
maps[y][x - 1] = 2//방문여부를 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
return False
너비우선탐색(BFS)
- Breadth First Search의 약자로 넓이 우선 탐색을 의미
- 하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정
while len(queue)>0:
count=len(queue)
for time in range (count):
now=queue.pop(0)
if now == dest:
return answer
for in 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
return answer
