[Python]1260번.DFS와 BFS(그래프이론, 그래프 탐색, BFS, DFS)

1260번: DFS와 BFS

💡문제

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

입력

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

풀이💬

처음엔 그냥 외워버려야지 라는 생각으로 공부했었는데 문제별로 상황별로, 입출력 조건별로 코드가 다 제각각 다르고 그때그때 맞춰서 코딩해야 할 것같다. DFS는 재귀를 이용해서 구현한다는 점, BFS는 큐에 노드들을 넣고 빼고 하면서 큐가 빌때까지 반복문을 돌린다는 점이 제일 핵심인듯 하다. 그리고 무한루프에 빠지지 않기 위해서는 언제나 base case에 대한 처리를 해줘야 한다(방문처리)

from collections import deque
import sys

input = sys.stdin.readline
node_num, edge_num, start_node = map(int,input().split())
graph = [[] for _ in range(node_num+1)]

#인접 리스트 생성
for _ in range(edge_num):
    start,end=map(int,input().split())
    graph[start].append(end)
    graph[end].append(start)

for gra in graph:
    gra.sort()

dfs_visited = [False]*(node_num+1)
bfs_visited = [False]*(node_num+1)

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


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

dfs(graph, start_node)
print()
bfs(graph, start_node)