[BOJ] 1260 - DFS와 BFS

문제 링크

1260-DFS와 BFS

문제 설명

입력

• 정점의 갯수 n
• 간선의 갯수 m
• 탐색 시작할 정점 v

출력

• DFS
• BFS

문제 풀이

개념 자체는 이해가 되는데 오랜만에 하려니깐 bfs구현하는데서 계속 애먹었다.
if not b_visited[g] 라고 해야하는데 if not b_visited라고 해서 계속 오류
그리고 처음에 sorted안해줘서 여기서도 좀 헤맸다.

import sys
from collections import deque
input = sys.stdin.readline

# 연결된 점끼리 리스트로 이루어짐
n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(len(graph)):
    graph[i].sort()

# 깊이 우선 탐색
d_visited = [False for _ in range(n+1)]
def dfs(v):
    d_visited[v] = True
    print(v, end=' ')
    for g in graph[v]:
        if not d_visited[g]:
            dfs(g)
            d_visited[g] = True

# 너비 우선 탐색
b_visited = [False for _ in range(n+1)]
def bfs(v):
	# 시작 노드를 큐에다가 먼저 삽입
    queue = deque([v])
    
    b_visited[v] = True

	# 큐에서 노드를 pop하고, 인접 노드들 탐색
    while queue:
        tmp = queue.popleft()
        print(tmp, end=' ')

        for g in graph[tmp]:
            if not b_visited[g]:
                b_visited[g] = True
                queue.append(g)

dfs(v)
print()
bfs(v)
print()

• DFS는 스택을, BFS는 큐를 사용

• 시작점부터 visited를 확인해서 인접 노드 중 False값을 가지는 점들을 재귀적으로 돌아다님

• 방문한 노드는 visited를 True로 변경