[3주차] BFS/DFS

3주차 알고리즘 TIL

 

✍ PlayData 3주차 BFS/DFS 수강 후 기록

 

BFS (Breadth First Search)

너비 우선 탐색.
하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정
시작 정점으로부터 가까운 정점을 먼저 방문하고,
멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 많이 사용

 

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