[BOJ] #1260 - DFS와 BFS

1260번: DFS와 BFS

 

 

** 문제 유형

• DFS, BFS

 

** 풀이

1. 기본적인 형태의 그래프를 단순히 DFS와 BFS로 탐색
2. 이 문제는 '정점 번호가 작은 것'을 먼저 방문해야 함
3. 모든 노드와 간선을 차례대로 조회하여 시간 복잡도는 O(N + M)
4. 큐 구현을 위해 collections 라이브러리의 deque 사용

 

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]) # BFS는 추가적인 큐가 반드시 필요함

    while q:
        v = q.popleft()

        if not(visited[v]):
            visited[v] = True

            print(v, end=' ')

            for e in adj[v]:
                if e not in q:
                    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)