[백준,Python]1260번 DFS와 BFS(DFS&BFS)

오늘 리뷰하는 문제는 DFS와 BFS의 기초를 공부하기에 좋은 문제라고 생각되는 문제입니다.

 

백준 1260번 문제를 Python으로 구현해보았습니다.

먼저, 간략하게 문제를 소개하자면, 

Input으로 정점 개수 N, 간선 개수 M, 시작 정점 V를 입력받고, M만큼 간선 들을 또 입력받고

Output으로 DFS와 BFS의 결과를 출력하는 문제입니다.

(자세한 문제 설명은 https://www.acmicpc.net/problem/1260로 확인하시면 됩니다.)

 

 

일단 간단하게 개념을 설명하자면, DFS는 깊이 우선 탐색으로 그래프가 있을 때 방문한 점에서 길이 있으면 길이 없을 때까지 계속 방문하고 없으면 처음 루트에서 다시 탐색을 진행하는 알고리즘이고, BFS는 너비 우선 탐색으로 시작 루트 기준으로 가능한 모든 길을 탐색한 후, 다음 레벨의 루트 탐색을 진행하는 알고리즘입니다.

 

 

코드는 다음과 같습니다.

def DFS(num):
    print(num,end=' ') # 처음 방문한 그 지점을 출력
    visited[num] = 1 #방문했을 때 그 방문리스트에 0으로 되어있을 텐데, 그것을 1로 바꾸어준다.
    for i in range(N+1):
        if visited[i]==0 and ablist[num][i]==1:
            DFS(i)

def BFS(num):
    result = [num]
    visited[num] = 0 # 아까 DFS함수를 돌면서 visited리스트의 인덱스값을 모두 1로 바꾸어 주었던 상태이므로 1인상태가 방문을 안한상태이니까 방문을 했을 경우 0으로 바꾸어준다.
    while(result):
        num = result[0]
        print(num,end=' ')
        del result[0]
        for i in range(N+1):
            if visited[i]==1 and ablist[num][i]==1:
                result.append(i)
                visited[i]=0

import sys
N, M,V = map(int, sys.stdin.readline().split())
#N이 정점 개수, M이 간선 개수, V가 시작정점 이라고 생각하고 그래프를 그리는 것이라고 생각하고 코딩 시작.
#간선 개수>
#그래프를 컴퓨터가 이해하도록 설계하려면 matrix로 설계를 해야 컴퓨터가 이해를 합니다.
#matrix를 설계와 동시에 초기화까지 시켜줍니다.

ablist = [[0]*(N+1) for _ in range(N+1)]
#내가 방문한 점을 또 방문하면 안되니까 visited라는 1차원 행렬을 만들어줍니다.
visited = [0 for _ in range(N+1)]
for i in range(M):
    a,b = map(int, sys.stdin.readline().split())
    ablist[a][b] =1
    ablist[b][a] =1

DFS(V)
print()
BFS(V)

 

기본적으로 함수에서 print기능을 할 수 있도록 방문했을 num를 출력하고, 다시 반복을 시켜 출력하도록 구현을 하였습니다.

 

여기서 중요한 부분이 DFS, BFS함수에서 조건을 만들 때인데, 저 코드를 풀어서 설명하자면 방문했던 지점이 아니고, input으로 정했던 간선이 일때 DFS에서는 재귀를 통해 DFS(i)를 해주었고, BFS에서는 재귀방법을 사용하는 것이 아니라, result라는 만든 리스트 안에 append를 해주고 visitied의 변수값을 변경시켜주어 방문했다는 표시를 한다는 점에서,

다시 말해 가장 큰 차이는 DFS재귀를 사용해서 다음정점 또 그다음 정점으로 간선을 통한 이동을 하는 반면, BFS는 임의의 리스트를 사용한 반복으로 탐색을 하기 때문에 인접 정점들을 모두 거치고 가기 때문에 결과가 다르게 나온다는 차이점이 있습니다.