백준 1260번 : DFS와 BFS

Python을 이용한 1260번 :DFS와 BFS에 대해서 포스팅하겠습니다.

1260번 문제설명

• 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
• 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 
• 정점 번호는 1번부터 N번까지이다.

접근방법

1. 그래프 초기화 및 입력 처리

• 그래프 데이터 구조: 이 코드에서는 딕셔너리를 사용하여 그래프를 표현하고 있습니다. 각 정점(key)은 연결된 다른 정점들의 리스트(value)를 가지고 있습니다.
• 입력 처리: stdin.readline()을 사용하여 정점의 수(n), 간선의 수(m), 탐색을 시작할 정점(v)을 입력받습니다. 이후 간선 정보를 입력받아 양방향 그래프를 구성합니다.
• 초기화: graph = {i: [] for i in range(1, n+1)}를 통해 각 정점에 대해 빈 리스트를 할당함으로써 그래프를 초기화합니다.

2. 깊이 우선 탐색(DFS)

• 함수 정의: dfs(v, graph, visited) 함수는 시작 정점 v와 그래프, 방문한 정점 리스트를 매개변수로 받습니다.
• 탐색 과정: 현재 정점에서 방문하지 않은 인접 정점을 찾아 계속해서 재귀 호출을 통해 탐색을 진행합니다.
• 종료 조건: 더 이상 방문할 인접 정점이 없으면 재귀 호출이 종료됩니다.
• 결과 반환: 방문한 정점들을 순서대로 저장한 리스트를 반환합니다.

3. 너비 우선 탐색(BFS)

• 함수 정의: bfs(v, graph, visited) 함수는 시작 정점 v와 그래프, 방문한 정점 리스트를 매개변수로 받습니다.
• 탐색 과정: 큐를 사용하여 너비 우선 탐색을 구현합니다. 현재 정점에 인접하고 아직 방문하지 않은 정점들을 큐에 추가합니다.
• 방문 순서: 큐에서 정점을 꺼내면서 방문 처리를 하고, 해당 정점에 인접한 미방문 정점을 큐에 추가합니다.
• 결과 반환: 방문한 정점들을 순서대로 저장한 리스트를 반환합니다.

4. 결과 출력

• 출력 형식: print(” “.join(map(str, dfs(v, graph, [v]))))와 print(” “.join(map(str, bfs(v, graph, []))))를 통해 DFS와 BFS의 결과를 공백으로 구분하여 출력합니다.
• 문자열 변환: map(str, ...)을 사용하여 정수 리스트를 문자열 리스트로 변환하고, join을 통해 문자열을 합쳐 출력합니다.

1260번 코드

# https://www.acmicpc.net/problem/1260
from sys import stdin

# 너비 우선 탐색(BFS) 함수
def bfs(v, graph, visited):
    queue = [v]  # 탐색을 시작할 정점을 큐에 추가
    while queue:
        temp = queue.pop(0)  # 큐에서 정점을 하나 꺼냄
        if temp not in visited:
            visited.append(temp)  # 방문하지 않았다면 방문 리스트에 추가
            # 현재 정점에 인접한 정점 중 방문하지 않은 정점을 큐에 추가
            queue.extend(i for i in graph[temp] if i not in visited)
    return visited  # 방문한 정점 리스트 반환

# 깊이 우선 탐색(DFS) 함수
def dfs(v, graph, visited):
    for i in graph[v]:  # 현재 정점에 인접한 정점들을 탐색
        if i not in visited:
            visited.append(i)  # 방문하지 않았다면 방문 리스트에 추가
            dfs(i, graph, visited)  # 재귀적으로 다음 정점 탐색
    return visited  # 방문한 정점 리스트 반환

# 입력 처리
n, m, v = map(int, stdin.readline().split())  # 정점의 수, 간선의 수, 시작 정점 입력
graph = {i: [] for i in range(1, n+1)}  # 그래프 초기화

# 그래프 구성
for _ in range(m):
    a, b = map(int, stdin.readline().split())
    graph[a].append(b)  # 간선으로 연결된 정점들을 추가
    graph[b].append(a)  # 양방향 그래프이므로 두 정점 모두에 추가

# 각 정점에 연결된 정점들을 정렬
for index in graph:
    graph[index].sort()

# DFS 결과 출력
print(" ".join(map(str, dfs(v, graph, [v]))))
# BFS 결과 출력
print(" ".join(map(str, bfs(v, graph, []))))