[ALGO] Search (BFS)

BFS(Breadth-First Search)

• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 (너비 우선 탐색)
• 데이터의 개수가 N개인 경우 O(N)
• 큐 자료구조를 이용
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
     
     tip. ‘방문 처리’는 큐에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크
     tip. BFS 알고리즘은 통상적으로 노드 번호가 낮은 순서부터 처리하도록 구현!
     
     

EX. BFS 예시 (방문 처리된 노드는 회색으로, 큐에서 꺼내 현재 처리하는 노드는 노란색으로 표현)

CODE

from collections import deque

def bfs(graph, start, visited):   # BFS 메서드 정의
  queue = deque([start])
  visited[start] = True   # 현재 노드를 방문 처리
  while queue:    # 큐가 empty일때까지 반복
    v = queue.popleft()
    print(v, end=' ')
    for i in graph[v]:    # 해당 원소와 연결된, 아직 방문되지 않은 원소들을 큐에 삽입
      if not visited[i]:
        queue.append(i)
        visited(i) = True
        
graph = [             # 각 노드가 연결된 정보를 리스트 자료형으로 표현
  [],
  [2,3,4],
  [1,5],
  [1,6,7],
  [1,8],
  [2,8,9],
  [3,7],
  [3,6],
  [4,5,9],
  [5,8]
]

visited = [False] * 9   # 각 노드가 방문된 정보를 리스트 자료형으로 표현

bfs(graph,1,visited)    # 정의된 BFS 함수 호출

1 2 3 4 5 6 7 8 9

기본 예제 1

code

from collections import deque

n, m = map(int,input().split())

graph = []
# 2차원 리스트의 맵 정보 받기
for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 방향 정의 (상,하,좌,우)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    # 큐가 빌 때까지 반복
    while queue:
        x,y = queue.popleft()
        # 현재 위치에서 네 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 공간 벗어난 경우 무시
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            # 갈 수 없는 곳이면 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] +1
                queue.append((nx,ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n-1][m-1]

print(bfs(0,0))

[출처] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 지음)