백준 : 1260 DFS와 BFS
백준 : 1260 DFS 와 BFS
문제 분석
M : 정점의 개수 , N : 간선의 개수, V : 탐색 시작할 정점
N개의 간선으로 연결된 정점의 번호
DFS, BFS 탐색 결과를 출력한다.
단, 1) 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 2) 입력으로 주어지는 간선은 양방향이다.
우리는 저 두 가지에서 키를 얻어야 한다. 첫 번째는 입력값이 주어졌을 때, 정렬을 통해 작은 숫자부터 탐색하도록 탐색 함수를 설계해야 한다는 것이며. 두 번째는 주어진 그래프는 무방향 그래프이다. 이 두가지에 유의해서 탐색 함수를 만들어보자.
최종 코드
인접 리스트를 활용하여 구현한 DFS, BFS 탐색
import sys
from collections import defaultdict, deque
#그래프 구조를 클래스 형태로 정의
class Graph:
def __init__(self):
#딕셔너리의 기본값을 리스트로 설정하여 인접 리스트 형태로 사용
self.graph = defaultdict(list)
def dfs (self, node):
result = []
visited = set()
def dfs_recur(n):
if n in visited:
return
visited.add(n)
result.append(n)
#인접 정점들을 오름차순으로 정렬하여 작은 번호부터 탐색한다
for v in sorted(self.graph[n]):
dfs_recur(v)
dfs_recur(node)
return result
def bfs (self, node):
result = []
queue = deque([node]) #BFS 탐색용 큐
visited = set([node])
while queue:
a = queue.popleft()
result.append(a)
for v in sorted(self.graph[a]):
if v not in visited :
visited.add(v)
queue.append(v)
return result
input = sys.stdin.readline
N, M, V = map(int, input().split())
graph = defaultdict(list) #전역 그래프 딕셔너리(입력용)
#간선 정보 입력받아 양방향 그래프 구성
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
g = Graph() #Graph 클래스 인스턴스 생성
g.graph = graph #외부에서 정의한 그래프와 클래스와 연결
print(*g.dfs(V))
print(*g.bfs(V))인접 행렬을 활용하여 구현한 DFS, BFS 탐색
import sys
from collections import deque
input = sys.stdin.readline
N, M, V = map(int, input().split())
# 인접 행렬 생성 (0으로 초기화된 N+1 x N+1 크기)
graph = [[0]*(N+1) for _ in range(N+1)]
# 간선 정보 입력받아 양방향 연결
for _ in range(M):
a, b = map(int, input().split())
graph[a][b] = graph[b][a] = 1
# 방문 여부 저장 배열 (1~N번 인덱스 사용)
visited = [False]*(N+1) #dfs 저장용
visited2 = visited.copy() #bfs 저장용
def dfs(V):
visited[V] = True
print(V, end=' ')
for i in range(1, N+1):
# 연결되어 있고 아직 방문 안 했으면 탐색
if graph[V][i] == 1 and visited[i] == 0:
dfs(i)
def bfs(V):
queue = [V]
visited2[V] = True
while queue :
V = queue.pop(0) # 큐에서 꺼낸 정점
print(V, end=' ')
for i in range(1, N+1):
# 연결되어 있고 아직 방문 안 했으면 큐에 추가
if (visited2[i]==0 and graph[V][i] == 1):
queue.append(i)
visited2[i] = True
dfs(V)
print()
bfs(V)인접 리스트 vs 인접 행렬
| 항목 | 인접 리스트 (dict/list) | 인접 행렬 (2D 배열) |
| 구조 | {1: [2, 3], 2: [1], ...} | [[0,0,1,0], [0,0,1,1], ...] |
| 메모리 | 간선 수에 비례 (O(V + E)) | 정점 수 제곱 (O(V^2)) |
| 탐색 속도 | 특정 정점의 이웃을 확인: 빠름 (O(인접 정점 수)) | 정점 사이 간선 존재 여부: 매우 빠름 (O(1)) |
| 공간 효율 | 간선이 적은 경우 유리 (희소 그래프에 좋음) | 간선이 많은 경우 유리 (조밀한 그래프에 좋음) |
| 코드 구현 | 정점마다 리스트 정렬 필요 | 행 순회로 정점 번호 순 정렬 자연스러움 |
| 예시 사용 | 대부분의 실전 문제 / 백준 등 문제 풀이에서 많이 씀 | 교육용, 정점 수 적은 문제에서 자주 등장 |
학습 내용 정리
1. 그래프를 인접 리스트로 표헌할때 defaultdict(list)를 사용하면 좋다
파이썬에서는 그래프를 딕셔너리로 표현할 때, 간선을 추가할 때마다 키 존재 여부를 일일이 확인하기 번거롭다. 이럴 때 collections.defaultdict(list)를 사용하면, 키가 존재하지 않아도 자동으로 빈 리스트를 만들어주기 때문에 깔끔하게 간선을 추가할 수 있다.
2. 인접 행렬을 수현 시 정점 번호가 1번부터 시작시, 인접 행렬은 N+1 x N+1 크기로 생성한다.
만약 graph = [[0]*N for _ in range(N)]으로 만든다면?
사용할 수 있는 인덱스 범위는 graph(N-1)까지이다. 이 방식으로 하게 된다면 정점 번호를 인덱스로 쓰기 위해 -1 연산이 추가적으로 들어가야 한다. 1번 정점은 0번 인덱스로! 이 경우 1) 불필요한 연산 2) 코드 가독성 저하 3) 실수할 확률이 높으므로 0의 배열은 버리는 방식을 채택하는것이 일반적이다.
3. DFS는 재귀/스택 으로 BFS는 큐로 구현한다
DFS는 깊이 우선 탐색이기 때문에 스택 구조로 작동하고, 파이썬에서는 재귀 함수로 쉽게 구현할 수 있다. BFS는 너비 우선 탐색으로 큐 구조가 필요하기 때문에 collections.deque를 활용하면 효율적인 큐 연산이 가능하다. pop(0) 대신 popleft()를 쓰는 이유는 시간 복잡도 때문인데, popleft()는 O(1), pop(0)은 O(n)이기 때문이다. 정확히는, pop을 하면 뒤 요소들을 앞으로 밀어야 하는데 deque는 양쪽에서 자료를 꺼내는걸 허용하기 때문에 별도로 데이터를 밀 필요가 없다.
4. 방문 체크는 visited 집합으로 빠르게 연산 가능하다
방문한 노드를 체크할 때는 set() 자료구조를 사용하는 것이 좋다. 리스트보다 검색 속도가 훨씬 빠르며, 방문 여부를 중복 없이 깔끔하게 처리할 수 있다. DFS와 BFS 모두 각각 visited를 따로 두어, 두 탐색이 서로 영향을 주지 않도록 설계했다.
5. "작은 정점부터 탐색"하려면 정렬을 해주자
문제에 따라 인접 노드 중 작은 번호부터 탐색해야 할 수도 있다. 이럴 땐 sorted()를 통해 인접 리스트를 정렬한 뒤 순회하면 된다. 이 정렬 로직은 DFS와 BFS 둘 다에 적용되며, 탐색 결과 순서에 큰 영향을 미친다.
6. 외부에서 만든 그래프를 클래스 내부에 연결하는 방식
이번 구현에서는 입력을 받아 만든 전역 graph 딕셔너리를 클래스 내부의 self.graph와 연결해주는 구조를 사용했다. 이를 통해 클래스는 외부 데이터와의 의존성을 유지하면서도, 내부 메서드에서 일관된 방식으로 그래프를 사용할 수 있다. 이 방식은 추후 다양한 데이터셋을 테스트할 때 유용하다.
7. 실수에서 배우는 것: 클래스 인스턴스 생성 vs 클래스 자체 참조
초기에는 g = Graph처럼 클래스를 참조만 하고 인스턴스를 생성하지 않아, 메서드 호출 시 self 인자를 넘기지 않아 생기는 TypeError를 경험했다. 이 실수를 통해 클래스의 인스턴스를 생성할 때는 반드시 g = Graph()처럼 괄호를 붙여야 한다는 점을 다시 한번 생각하게 되었다.