3주차 - 너비우선탐색/깊이우선탐색

1. 너비우선탐색(BFS; Breadth First Search)

: 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회탐색

→ 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용

while len(queue)>0:
	count = len(queue)		# 같은 거리에 있는 큐 개수
    for time in range(count):		# 같은 거리에 있는 큐 개수만큼 검사
    	now = queue.pop(0)
        if now == destination:
        	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

 

2. 깊이우선탐색(DFS; Depth First Search)

: 한 방향으로 계속 가다가 더 이상 갈 수 없을 때, 다시 가장 가까운 갈림길로 돌아와 다른방향으로 탐색

→ 모든 노드를 방문하고자 할 경우에 사용 

 

while len(stack) > 0:
	now = stack.pop()
    if now == destination:
    	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
    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

 

강의 들으면서 코드 따라 적고 있지만 개인적이로 강의가 너무 구린것 같다 ㅠ