백준 1260번 DFS와 BFS | python | 그래프 알고리즘

문제

링크

풀이

아무 스킬 없이 dfs와 bfs를 구현하면 되는 문제이므로 해설은 생략하겠다.

한 번 짚어볼 만한 것은 인접리스트를 활용해 그래프 정보를 저장하는 방식이다. 각 노드마다 연결된 모든 노드를 기입하기 위해 graph[a].append(b) 뿐만 아니라 graph[b].append(a) 도 해주어야함을 잊지 말자.

그래프를 표현하는 대표적인 방식인 인접리스트와 인접행렬에 대한 설명은 여기를 참고해보면 좋다.

from collections import deque

n, m, v = map(int, input().split())
# n 정점의 개수
# m 간선의 개수
# v 탐색을 시작할 번호

graph = [[] for _ in range(n + 1)]
visited_dfs = [0] * (n + 1)

for i in range(m):
    a, b = map(int, input().strip().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()


def dfs(n):
    visited_dfs[n] = 1
    print(n, end=" ")
    for i in graph[n]:
        if not visited_dfs[i]:
            dfs(i)


dfs(v)
print()

visited_bfs = [0] * (n + 1)


def bfs():
    q = deque()
    q.append(v)
    visited_bfs[v] = 1
    while q:
        n = q.popleft()
        print(n, end=" ")
        visited_bfs[n] = 1
        for i in graph[n]:
            if not visited_bfs[i]:
                q.append(i)
                # visited_bfs[i] = 1


bfs()

🦾 깨달은 점

역시 퍼블릭하게 정리해 나가야 기억에 오래남는 것 같다. 일주일동안 미뤄둔 백준 포스트 오늘 다 올려야겠다. 이렇게 말하면 올리겠지 ?