백준24445🐨너비 우선 탐색(BFS)과 문제 풀이: 알고리즘 수업

https://www.acmicpc.net/problem/24445

1. 너비 우선 탐색(BFS)란?

BFS 개념

BFS는 그래프 탐색 알고리즘 중 하나로, 특정 시작 정점으로부터 인접한 모든 정점을 우선적으로 탐색한 뒤, 다음 인접한 정점들을 차례대로 탐색하는 방식이다. BFS는 주로 큐(queue) 자료구조를 사용하며, 그래프가 트리 구조일 때는 레벨별로 노드를 탐색하는 것과 유사하다.

BFS의 주요 특징은 다음과 같다:

최단 경로 탐색에 유용하다. 모든 간선의 가중치가 동일할 때 최단 경로를 찾을 수 있다.
큐(queue) 자료구조를 사용하여 FIFO(First In First Out) 방식으로 정점을 탐색한다.
그래프의 레벨 순 탐색이 이루어지며, 이를 통해 모든 정점을 빠짐없이 방문할 수 있다.

BFS의 동작 과정

BFS 알고리즘의 기본적인 작동 과정은 다음과 같다:

시작 정점을 큐에 삽입하고 방문 표시를 한다.
큐가 비어있지 않은 동안 반복한다.
- 큐에서 정점을 하나 꺼내고, 해당 정점의 인접 정점들을 탐색한다.
- 아직 방문하지 않은 정점들을 큐에 추가하고 방문 표시를 한다.

이번 문제에서는 내림차순으로 인접 정점을 방문한다는 특징이 있다.

2. 문제 이해

주어진 문제는 무방향 그래프에서 시작 정점으로부터 BFS를 수행하여 각 정점의 방문 순서를 출력하는 것이다. 내림차순으로 인접한 정점을 방문해야 하며, 방문할 수 없는 정점은 0으로 표시해야 한다.

입력 및 출력 설명

입력: 정점 수 , 간선 수 , 시작 정점 , 그리고 개의 간선 정보.
출력: 각 정점의 방문 순서를 출력하며, 방문할 수 없는 정점은 0을 출력한다.

예제 입력과 출력의 의미를 이해하고, 정점 방문 순서를 올바르게 출력해야 한다.

3. 문제 풀이 접근

이 문제를 해결하기 위해 다음과 같은 단계로 접근할 수 있다:

그래프 생성: 인접 리스트를 이용하여 그래프를 생성한다. 각 정점의 인접 리스트는 내림차순으로 정렬해야 한다.
BFS 구현: 큐를 사용하여 BFS를 수행하고 각 정점의 방문 순서를 기록한다.
결과 출력: 방문 순서를 기준으로 결과를 출력한다.

4. 코드 구현

아래는 이 문제를 해결하기 위한 Python 코드이다. BFS 알고리즘을 구현하고, 주어진 조건에 맞게 그래프를 탐색한다.

from collections import deque, defaultdict

n, m, r ,*d= map(int, open(0).read().split())
graph = defaultdict(list)

for i in range(0,m<<1,2):
    u, v = d[i],d[i+1]
    graph[u].append(v)
    graph[v].append(u)

# 정렬
for key in graph:
    graph[key].sort(reverse=True)

def bfs(start):
    visited = [-1] * (n + 1)  # 방문 순서를 저장 리스트 (-1은 미방문)
    queue = deque([start])
    visited[start] = 1  # 시작 정점 방문 표시 및 순서 기록
    order = 1

    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if visited[neighbor] == -1:
                order += 1
                visited[neighbor] = order
                queue.append(neighbor)

    return visited

visit_order = bfs(r)

for i in range(1, n + 1):
    if visit_order[i] == -1:
        print(0)
    else:
        print(visit_order[i])

코드 설명

그래프 입력 및 생성:
- graph는 각 정점의 인접 정점들을 저장하는 딕셔너리 형태의 인접 리스트이다. 간선을 입력받을 때 각 정점의 리스트에 다른 정점을 추가한다.
- 문제에서 요구한 대로 인접 정점을 내림차순으로 정렬한다.
BFS 구현:
- bfs 함수는 큐와 방문 리스트를 사용하여 시작 정점으로부터 BFS를 수행한다.
- visited 리스트는 방문 순서를 기록하기 위해 사용된다. 초기값은 -1로 설정되어 있으며, 방문 시 방문 순서를 기록한다.
결과 출력:
- 방문하지 못한 정점은 0을 출력하도록 조건을 설정하여 최종 결과를 출력한다.

5. 작동 과정

주어진 입력 예제에서 BFS의 작동 과정을 설명해보자.

시작 정점 1부터 BFS를 시작한다. 1의 인접 정점은 4와 2이며, 내림차순으로 방문해야 하므로 정점 4를 먼저 방문한다.
정점 4에 방문한 후, 4의 인접 정점 3을 방문한다.
그 후 정점 2를 방문하고, 방문할 수 있는 정점이 없으면 탐색을 종료한다.
방문하지 않은 정점(여기서는 정점 5)은 방문 순서가 0이 된다.

6. 결론

BFS는 큐를 활용하여 그래프의 모든 정점을 순차적으로 탐색하는 알고리즘.
모든 간선의 가중치가 동일한 경우 최단 경로를 찾을 때 유용함.
문제의 요구사항에 따라 인접 정점을 내림차순으로 방문하도록 구현한 것이 핵심.

저작자표시 비영리 변경금지

붉은 각설탕