[백준 1260 파이썬 ] DFS와 BFS

문제

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

입력

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

출력

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

풀이

DFS는 깊이 우선 탐색으로 인접 노드의 가장 깊은 레벨 까지 먼저 진행하기 때문에

재귀 함수 형태로 구현이 가능하다.

BFS는 너비 우선 탐색으로 큐를 이용하여 큐에 현재 노드를 넣고 시작하여 큐의 pop한 노드의 인접 노드를

큐에 넣고 다시 반복하는 것으로 구현이 가능하다.

우선 노드간의 연결 상태인 간선을 나타낼 2차원 리스트 matrix를 생성한다. 노드의 값과 인덱스를 맞추기 위해

n+1의 크기로 2차원 배열을 생성한다.

그리고 해당 노드를 탐색 했는지 체크하기 위한 1차원 리스트 visit을 생성한다.

 

이제 DFS탐색에서는 현재 노드를 탐색했다고 체크하기 위해 visit[v]를 1로 바꾸고 출력한다.

그리고 반복문을 통해 방문하지 않은 연결된 노드를 찾아 다시 함수를 수행한다.

이렇게 깊이 우선 탐색을 구현할 수 있다.

 

BFS탐색에서는 queue에 현재 노드를 넣고 시작한다.

그리고 탐색했다는 것을 나타내기 위해 visit[v]를 0으로 바꿔준다.

(DFS탐색으로 인해 전부 1로 바뀐 상태였다.)

이제 큐를 pop하여 나온 값을 출력하고 방문하지 않은 인접 노드를 큐에 추가한다.

큐가 남아있을 때까지 반복한다. 

이렇게 너비 우선 탐색을 구현할 수 있다.

 

import sys
n, m ,v = map(int, sys.stdin.readline().rstrip("\n").split())
matrix = [[0]*(n+1) for _ in range(n+1)]
for i in range(0,m):
    num1, num2 = map(int, sys.stdin.readline().rstrip("\n").split())
    matrix[num1][num2] = 1
    matrix[num2][num1] = 1

visit = [0]*(n+1)

def dfs(v):
    visit[v]=1
    print(v,end=" ")
    for i in range(1,n+1):
        if(visit[i]==0 and matrix[v][i]==1):
            dfs(i)

def bfs(v):
    queue=[v]
    visit[v]=0
    while queue:
        v = queue.pop(0)
        print(v,end=" ")
        for i in range(1,n+1):
            if(visit[i]==1 and matrix[v][i]==1):
                queue.append(i)
                visit[i]=0

dfs(v)
print()
bfs(v)