Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

차근차근

[백준 1260] DFS와 BFS 본문

대학교/Algorithm

[백준 1260] DFS와 BFS

SWKo 2020. 9. 5. 23:23

0. 제목

  • 백준 1260 DFS와 BFS
  • BOJ 1260 DFS와 BFS
  • Python 1260 DFS와 BFS

1. 문제

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

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net


2. 풀이

  • dfs의 경우 인접한 정점들을 차례로 탐색할 수 있도록 재귀를 사용한다.
  • bfs의 경우 deque를 사용한다. 탐색을 마치면 pop을 하고 인접한 정점 중 방문하지 않았던 점은 append로 deque에 추가해줌으로써 deque가 빌 때까지 반복하여 수행한다.
  • 방문여부를 나타내는 배열은 각 탐색을 시작하기 전에 False로 초기화를 시켜준다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections import deque
 
def dfs(v):
    print(v, end=' ')
    visited[v] = True
    for e in adj[v]:
        if not(visited[e]):
            dfs(e)
            
def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if not(visited[v]):
            visited[v] = True
            print(v, end=' ')
            for e in adj[v]:
                if not visited[e]:
                    q.append(e)
                    
n, m, v = map(int, input().split())
adj = [[] for _ in range(n + 1)]
 
for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)
    
for e in adj:
    e.sort()
    
visited = [False* (n + 1)
dfs(v)
print()
visited = [False* (n + 1)
bfs(v)

'대학교 > Algorithm' 카테고리의 다른 글

[백준 2606] 바이러스  (0) 2020.09.08
[백준 1697] 숨바꼭질  (0) 2020.09.06
[백준 2110] 공유기 설치  (0) 2020.09.04
[백준 1874] 스택 수열  (0) 2020.09.03
[백준 1302] 베스트 셀러  (0) 2020.09.02
Comments