BFS(너비 우선 탐색)

BFS(Breadth First Search, 너비 우선 탐색)

큐 활용

시작점의 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문

인접한 정점들을 탐색한 후, 차례로 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐 활용

인접 리스트로 구현했을 때 O(|V| + |E|), 인접 행렬로 구현했을 때 O(|V^2|)의 시간복잡도를 가진다.

인접 리스트는 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장

인접 행렬은 2차원 배열을 이용해 그래프의 간선 정보를 저장

 

🌿 인접 리스트와 인접 행렬의 예시

양방향 그래프

---

🐋 BFS 코드 예시

 

from collections import deque

def BFS(G, v) : # 그래프 G, 탐색 시작점 v
  visited=[0]*n			# n : 정점의 개수
  queue=deque()			    # 큐 생성
  queue.append(v)		# 시작점 v를 큐에 삽입
  while queue : 		# 큐가 비어있지 않은 경우
    t=queue.popleft()		# 큐의 첫번째 원소 반환
    if not visited[t] :		# 방문되지 않은 곳이라면
      visited[t]=True		# 방문한 것으로 표시
      for i in G[t] :			# t와 연결된 모든 선에 대해
        if not visited[i] :	# 방문하지 않은 곳이라면(생략가능)
          queue.append(i)		# 큐에 넣기

연결된 노드 방문

위의 코드는 deque를 활용함.

popleft()는 pop()보다 효율이 더 좋음.

 

# '거리두기 확인하기' 문제 중
def bfs(y, x, places):
    que = deque([(y, x)])
    visited = [[-1] * 5 for i in range(5)]
    visited[y][x] = 0
    while que:
        pos = que.popleft()
        for a, b in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            dx = b + pos[1]
            dy = a + pos[0]
            if not isin(dx, dy): continue
            if visited[dy][dx] == -1 and places[dy][dx] != "X":	# 방문 x와 조건
                que.append((dy, dx))  # 범위체크
                visited[dy][dx] = visited[pos[0]][pos[1]] + 1

    return visited

상하좌우로 bfs 탐색

visited는 방문 기록 & 거리 두 가지 의미

 

// 백문 '11403. 경로 찾기' 문제 중에서
private static void bfs(int start) {
        front=rear=-1;

        check[start]=true;
        q[++rear]=start;

        while(front != rear){
            cur=q[++front];
            for(int i=0; i<N; i++){
                if(map[cur][i] == 1){
                    if(!isCycle && i == start){
                        isCycle=true;
                    }
                    if(!check[i]){
                        check[i]=true;
                        q[++rear]=i;
                    }
                }
            }
        }

deque를 쓰지 않고 푼다.(bfs는 죄다 deque 쓰던데 처음 봄)

 

 

 

참고 👉 SW expert academy, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 2