1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
<내 코드>
def dfs(v):
done.append(v) # 방문한 노드 추가
# print(done)
# 해당 행(노드) 탐색(1행 ~ n행)
for i in range(1, n+1):
if (i not in done) and (matrix[v][i] == 1):
dfs(i)
return done
def bfs(start):
queue = [start]
done = [start]
while queue:
v = queue.pop(0)
for i in range(1, n+1):
if (i not in done) and (matrix[v][i] == 1):
queue.append(i)
done.append(i)
return done
n, m, v = map(int, input().split())
done = []
matrix = [[0]*(n + 1) for _ in range(n + 1)]
for _ in range(m):
x, y = map(int, input().split())
matrix[x][y] = 1
matrix[y][x] = 1
print(*dfs(v))
print(*bfs(v))
그래프를 표현하기 위해 여기서는 '인접 행렬' 방식으로 구현했다. DFS(깊이 우선 탐색)은 주로 스택과 재귀를 통해 구현하고 BFS(너비 우선 탐색)은 큐로 구현을 많이 한다.
반응형
'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글
| [백준 2606] 바이러스 - Python (그래프 탐색, DFS) (0) | 2020.08.30 |
|---|---|
| [백준 2178] 미로 탐색 - Python(BFS, 그래프 탐색) (0) | 2020.08.30 |
| [백준 1783] 병든 나이트 - Python (그리디 알고리즘) (0) | 2020.08.28 |
| [백준 1138] 한 줄로 서기 - Python (그리디 알고리즘) (0) | 2020.08.28 |
| [백준 2217] 로프 - Python (그리디 알고리즘, 정렬) (0) | 2020.08.28 |