[파이썬] BFS 해결하기

다음은 연결되어 있는 두 개의 정점 사이의 간선을 순서대로 나열 해 놓은 것이다. 모든 정점을 깊이 우선 탐색하여 화면에 너비우선 탐색 경로를 출력하시오. 시작 정점을 1로 시작하시오.

 

 

입력

입력 파일의 첫 번째 줄에는 테스트 케이스 T(1 <= T <= 10)의 개수가 주어지며, 각 테스트 케이스의 첫 줄에는 정점의 개수 N, 간선의 개수 M(1 <= N. M <= 10000)가 주어진다. 그 다음 M줄에 거쳐 인접한 두 정점이 주어진다.

 

입력 예시

1

7 8

1 2

1 3

2 4

2 5

4 6

5 6

6 7

3 7

 

출력

모든 정점을 너비 우선 탐색하여 경로를 출력하시오. 시작 정점은 1로 한다.

 

출력 예시

1 2 3 4 5 7 6

 

 

🍟 나의 풀이

 

from collections import deque

def bfs(v):
    queue = deque()     # 큐 생성
    # 시작 정점 1을 추가
    queue.append(1)
    visited[1]=1

    while queue:
        v = queue.popleft()
        print(v)                	# 삭제 후 출력
        for i in lst[v]:        	# 정점의 값(인접한 정점) 탐색
            if visited[i] != 1:     # 방문한 적 없으면
                queue.append(i)     # 정점 추가
                visited[i] = 1      # 방문 처리


T = int(input())                    # 테스트 케이스 수

for tc in range(T):
    N, M = map(int, input().split())    # 정점의 개수, 간선의 개수
    visited = [0] * (N + 1)           # 정점을 1부터 시작하려고 +1만큼 만듦
    lst = [[] for _ in range(N + 1)]  # 인덱스 : 정점, 값 : 인접한 정점 값

    for i in range(M):                  # 인접한 두 정점 정보가 주어짐
        x, y = map(int, input().split())
        # 양방향으로 연결함
        lst[x].append(y)
        lst[y].append(x)
    
    bfs(1)        # bfs함수 호출

 

1. 시작 정점 1을 queue에 삽입, visited에 방문 처리한다.

2. queue에서 가장 맨 앞에 있는 값을 pop하고 출력한다.

3. 정점 v의 값(인접한 정점)을 for 반복문을 통해 탐색한다.

4. 정점 i를 방문한적 없다면 queue에 추가하고 visited[i]=1

2 ~ 4 과정을 queue에 값이 있을 동안 반복.

 

 

 

 

문제 출처 SW expert academy