[그래프 #2] 인접 행렬, 인접 리스트를 활용한 BFS 문제풀이 방법

Queue

• BFS에서 주로 사용되는 자료구조
• FIFO (First-In, First-Out) 구조 / 먼저 들어온 데이터가 먼저 나감
• 큐에 노드를 담아 순서대로 방문, 방문하지 않은 노드를 큐에 삽입하여 탐색

 

BFS step

1. queue 준비
   • 시작 노드 queue에 삽입
2. (cycle이 생길 시) visited 준비
   • 시작 노드를 예약 후 시작
3. BFS 동작
   • queue에 가야하는 / 예약된 노드가 있는 동안 반복
   • 지금 방문하는 노드를 queue의 맨 앞에서 빼와서 저장 → now
   • now에서 갈수 있는 노드들을 판단, 갈 수 있다면 queue에 새로 삽입 + 예약
   • (방문 기록) 필수

---

시간복잡도 비교

1. 재귀 함수

• O(호출되는 함수의 개수)
• 일반적으로 O(n) 또는 O(2^n) 정도의 시간 복잡도
  • 재귀 함수의 시간 복잡도는 문제의 크기와 관련
  • 재귀 함수가 많이 호출되면 스택의 크기가 커지고 시간 복잡도도 증가
  • 재귀 함수는 깊이가 깊어질수록 시간 복잡도가 증가

2. 깊이 우선 탐색 (DFS)

• DFS의 시간 복잡도는 트리에서는 O(n)이고, 그래프에서는 O(n + m)  <- 인접리스트로 구현 시
• 더 깊은 노드에 도달할수록 시간 복잡도가 증가

3. 너비 우선 탐색 (BFS)

• 트리에서는 O(n), 그래프에서는 O(n + m) (n은 정점의 수, m은 간선의 수) <- 인접리스트로 구현 시
• BFS는 레벨 단위로 탐색 → 길이가 짧은 경로를 찾는 것이 가능

---

/* Queue 사용법 */

queue<int>q;  // Queue 생성

q.push(1);
q.push(2);
q.push(3);

// queue의 맨 앞의 값을 확인
cout << q.front();  -> 1
// queue에 몇 개의 요소가 있는 지 확인
cout << q.size();   -> 3
// queue가 비어있으면 true(1) or false(0)
cout << q.empty();  -> 0
// queue의 맨 앞의 요소를 삭제
// python과 다르게, 가져오는 것과 삭제하는 것을 같이 해주어야 함
q.pop();

 

인접 행렬로 BFS하기

/*
7 6
0 1
0 2
1 3 
1 4
4 5
4 6
*/

int N; // node 개수
int M; // edge 개수

int adj[10][10] // adjacent matrix

void BFS(int start){
	
	queue<int>q;  // #1. queue 생성
	
	q.push(start); // queue에 시작 노드 삽입
	
	int visited[10] = {0, };  // #2. (cycle 생길 시) visited 준비

	visited[start] = 1;  // 시작 노드를 방문 처리

	while (){
		// 1. 대기열에서 맨 앞의 노드를 방문 + queue에서 삭제
		int now = q.front();
		q.pop();

		// 2. 갈 수 있는 노드들을 판단하고, queue에 삽입
		// 큐에 삽입 -> 미래에 갈 노드를 예약
		for (int next=0; next<N; next++){
	
			if (mat[now][next] == 0) continue;
			// now-next에 연결이 되어 있다면 삽입
			
			if (visited[next] == 1) continue;
			// 예약되어 있는 노드나 방문한 노드라면, 예약을 걸지 않겠다.

			q.push(next);
		}
	}

}

 

인접 리스트로 BFS하기

int N;
int M;

vector<int>al[10];

void BFS2(int start){

	queue<int>q;
	q.push(start);

	while(!q.empty()){
		int now = q.front();
		q.pop();
		
		cout << now << " ";

		for (int i=0; i<al[now].size(); i++){
			int next = al[now][i];
			q.push(next);
		}
	}

}

int main() {
    cin >> N >> M;

    // 간선 정보 
    for (int i = 0; i < M; i++) {
        int from, to;
        cin >> from >> to;
        al[from].push_back(to); 
        al[to].push_back(from); 
    }

    BFS(0);  // BFS(시작 노드)
}

 

 

---

Python으로 BFS하기 (2차원) 

from collections import deque

class loc:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Sol:
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    def __init__(self):
        self.N, self.M = map(int, input().split()) # N : 높이, M : 너비

        # 맵 정보 저장
        self.arr = [list(map(int, input().split())) for _ in range(self.N)]

        # 시작 위치
        sx, sy = 0, 0

        self.BFS(sx, sy)

    def BFS(self, sx, sy):
        # 1. 변수 초기화
        q = deque()
        visit = [[False]*self.M for _ in range(self.N)]

        # 2. 초기값 설정
        visit[sx][sy] = True # 첫 노드 방문 완료
        q.append(loc(sx, sy)) # 첫 노드 정보 등록

        step = 0    # 현재 BFS를 몇 level만큼 진행했는 지 저장
        curSize = 0 # BFS 시작 전, 현재 queue의 크기

        while q:
            curSize = len(q)

            # 현재 queue 크기만큼 BFS 진행 --> step을 파악하기 위함
            for c in range(curSize):
                target = q.popleft()

                # 방향 탐색 코드
                for i in range(4):
                    nx = target.x + self.dx[i]
                    ny = target.y + self.dy[i]

                    # 제한 조건 검사
                    if not (0 <= nx < self.N and 0 <= ny < self.M): continue # 인덱스 범위 확인
                    if (visit[nx][ny] == True): continue # 방문한 노드 건너뛰기
                    if (self.arr[nx][ny] == '종료조건'): return

                    visit[nx][ny] = True
                    q.append(loc(nx, ny))

            # 기존 queue에 있던 노드 탐색을 완료 --> step 더하기
            step += 1

        return None

 

 

Python으로 BFS하기 (1차원)

from collections import deque

def bfs(start_v, end_v):
    global adj_lst

    # 1. 변수 초기화
    q = deque()
    visit = [False] * (V + 1)

    # 2. 초기값 설정
    visit[start_v] = True
    q.append(start_v)

    step = 0 # 현재 BFS를 몇 level만큼 진행했는 지 저장
    curSize = 0 # BFS 시작 전, 현재 queue의 크기 저장

    # 3. BFS 진행
    while q:
        curSize = len(q)

        for c in range(curSize):
            cur_v = q.popleft()

            # 현재 queue 크기만큼 BFS 진행 --> step을 파악하기 위함
            for next_v in adj_lst[cur_v]:
                if (visit[next_v] == True): continue # 재방문이면 건너뛰기
                if (next_v == end_v): return (step+1) # target node에 도달 시 종료
                visit[next_v] = True
                q.append(next_v)

        step += 1 # 1 level을 내려간 것을 step에 표시
    return 0 # 문제 조건 : 못 찾을 시 0 return


V, E = map(int, input().split())

adj_lst = [[] for _ in range(V + 1)] # 인접 리스트로 노드 관계를 저장

for _ in range(E):
    v1, v2 = map(int, input().split())
    adj_lst[v1].append(v2) 
    adj_lst[v2].append(v1) # 양방향 그래프일 경우, 추가

S, G = map(int, input().split()) # 시작 노드가 S, 끝 노드가 G
ans = bfs(S, G)