[BOJ/백준] 1260. DFS와 BFS (Python)

🔎 문제

🔗 백준 1260번 DFS와 BFS

💡 풀이

아~ 그냥 단순 DFS, BFS네 하고 쓱쓱 써내려갔는데 아뿔싸 역시 문제는 꼼꼼히 읽어야 한다.

❗방문할 수 있는 정점이 여러개인 경우, 정점 번호가 작은것 먼저 방문

for w in sorted(graph[v]):

이렇게 오름차순으로 정렬 후에 방문해야 한다.

❗입력으로 주어지는 간선은 양방향

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

양방향 그래프 이므로 이렇게 둘 다 할당해 주어야 한다.

📃 소스코드

import sys
import collections
input = sys.stdin.readline
graph = collections.defaultdict(list)

def dfs(v, visited = []):
    visited.append(v)
    for w in sorted(graph[v]):
        if not w in visited:
            visited = dfs(w, visited)
    return visited
    
def bfs(v, visited = []):
    visited.append(v)
    queue = collections.deque()
    queue.append(v)
    while queue:
        w = queue.popleft()
        for w in sorted(graph[w]):
            if w not in visited:
                visited.append(w)
                queue.append(w)
    return visited

v, e, start = map(int, input().split())

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

print(*dfs(start))
print(*bfs(start))

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️