Python 백준 1260 - DFS와 BFS (DFS & BFS) 풀이

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

풀이과정

일단 먼저 dfs와 bfs 알고리즘 자체는 외워두는 게 코딩하는데에 편하다.

동빈나님 유튜브를 통해 이미 dfs, bfs 알고리즘 형태는 외웠다. 영상 한 번만 시청해도 바로 외워질 정도로 정리가 잘되어 있음!!

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=WL&index=5&t=1835s

(feat. 동빈나님 감사함돵~유튭 알고리즘 영상 너무 이해가 잘됨)

원리를 알면 저절로 잘 외워지는 느낌!!

먼저 나는 작은 수부터 출력이 된다는 전제를 잊어버려 sorting을 하지 않고 하는 바람에 시간이 꽤나 걸렸다.

급하게 sorting을 했는데 index runtime error가 발생해버림...

어디선가 내가 index처리를 잘못한 느낌...

sorting하는 부분에서 인덱스를 잘 못 넘겨버려 에러 원인 발견!!

 

아래는 나의 풀이이다. 

 

풀이

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


def dfs(graph, start, visited):
    visited[start]=True
    print(start, end=' ')
    for i in graph[start]:
        if not visited[i]:
            dfs(graph, i, visited)
    

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(N+1):
    graph[i].sort()
    # print(i, graph[i])

# print(graph)
visited_dfs=[False]*(N+1)
visited=[False]*(N+1)
dfs(graph, V, visited_dfs)
print("")
bfs(graph, V, visited)