백준 1260 DFS와BFS 파이썬

백준 1260 DFS와BFS 풀이

접근방식

1. 2차원 리스트로 노드 간 연결 정보를 저장합니다.
2. 양방향이기 때문에 양쪽 다 저장해줍니다.
3. 문제에서 제시한 조건 중 방문 가능한 정점이 여러 개인 경우, 번호가 낮은 것부터 방문해야 합니다.
4. 따라서 시작 전에 graph의 정점을 오름차순으로 정렬해줍니다.
5. 방문 처리를 위해 visited 리스트를 만들어줍니다.
6. dfs의 경우, 시작 노드인 v를 방문처리 해주고, 해당 위치의 리스트를 탐색해서
7. 재귀함수를 실행해줍니다.
8. bfs의 경우, deque을 이용해서 시작 노드를 먼저 append 시켜줍니다.
9. 이후 popleft 해주면서 큐에 다시 넣어주고 출력하는 것을 반복합니다.

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()

n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    # 양방향 저장
    graph[x].append(y)
    graph[y].append(x)


 # 작은 것부터 방문
for i in range(n+1):
    graph[i].sort()


 # DFS

visited = [False for _ in range(n+1)]

def dfs(graph, v, visited):
    # 현재 노드 방문처리
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            # 재귀함수
            dfs(graph, i, visited)

 # BFS

def bfs(graph, v, visited):
    queue = deque([v])
    visited[v] = True
    while queue:
        i = queue.popleft()
        print(i, end = ' ')
        for j in graph[i]:
            if not visited[j]:
                queue.append(j)
                visited[j] = True

dfs(graph, v, visited)
print()
 # visited함수를 이미 dfs에서 활용했기 때문에 재선언
visited = [False for _ in range(n+1)]
bfs(graph, v, visited)

해당 문제는 실버 2 난이도의 DFS, BFS 문제였습니다.

두 알고리즘을 비교하는 데에 있어서 좋은 문제라고 생각합니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady