[백준][1260] DFS와 BFS - Python3

1. 문제 설명

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

입력

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

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1

4 5 1

1 2

1 3

1 4

2 4

3 4

예제 출력 1

1 2 4 3

1 2 3 4

 

2. 접근 방법 및 풀이

- 문제 이름 자체가 DFS와 BFS이니 만큼 해당 알고리즘을 사용하면 됩니다. 저는 유튜브 동빈나 님의 영상을 보고 정리해두었던 DFS, BFS 함수를 그대로 가져와서 사용했습니다! 

- 프로그래머스와 다르게 입력을 다듬어서 그래프를 만들어주어야 합니다.

from collections import deque
 
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end= ' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
 
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    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
 
N, M, V = map(int, input().split())
 
graph = [ [] for _ in range(N+1)]  # 그래프 초기화
 
for i in range(M):  # 그래프 값 채우기
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)
    
for m in graph:    # 연결된 정점의 번호 오름차순 정렬
    if len(m) < 2:
        continue
    else:
        m.sort()
    
visited = [False] * (N+1)
dfs(graph, V, visited)
print()
visited = [False] * (N+1)
bfs(graph, V, visited)

3. 후기

- 제가 알고리즘에 대해 완전히 이해하고 있지 못해서 풀이가 허술한 느낌입니다. 열심히 공부해서 알고리즘과 자료구조에 관해 공부한 내용도 정리해서 포스팅 하도록 노력하겠습니다.

- 사실 DFS, BFS는 문제를 풀 때마다 새로운 느낌입니다..... 많이 풀다 보면 눈이 뜨이지 않을까요..!

- 드디어 코드를 복사할 수 있게끔 포스팅 하는 방법을 알아냈습니다..! :)