파이썬 / BOJ 백준 알고리즘 / 1260번 DFS와 BFS 문제 및 풀이

파이썬 / 백준 알고리즘 / 1260번 DFS와 BFS 문제 및 풀이

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

문제

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

 

입력

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

 

출력

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

 

 

예제 입력 및 출력

 

문제 풀이

너비우선탐색(BFS, Breadth First Search)와 깊이우선탐색(Depth First Search)의 전형적인 기초 문제입니다. 이 두 알고리즘은 그래프를 탐색하기 위한 알고리즘으로 모든 정점을 탐색하기 위해 사용됩니다.

DFS는 한 경로로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 경로로 탐색하는 방식이고,(스택의 방식을 이용함, 스택은 기본 동작이라 스택 자료 구조를 이용할 필요는 없음)
BFS는 갈림길에 연결되어 있는 모든 경로를 한번씩 탐색한 뒤 다시 연결되어 있는 모든 경로를 넓게 탐색하는 방식입니다. (자료 구조 큐 또는 덱 구조를 이용해야 함)

예를 들어 아래와 같은 그래프에서 DFS 동작은 다음과 같습니다. 
1) 정점 1에서부터 검색 시작
2) 1에 연결된 정점 2,3,4 중 가장 작은 수인 2(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨)를 방문
3) 2에 연결된 정점 4를 방문
4) 4에 연결된 정점 3을 방문
5) 더이상 방문할 정점이 없으므로 종료
- 결국 1->2->4->3 순으로 방문하게 됩니다

 

예를 들어 아래와 같은 그래프에서 BFS 동작은 다음과 같습니다.
1) 정점 1에서부터 검색 시작 
2) 정점 1과 연결된 2를 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
3) 정점 1과 연결된 3을 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
4) 정점 1과 연결된 4를 검색 
- 결국 1->2->3->4 순으로 방문하게 됩니다. 

 

전체 코드

from collections import deque

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

def bfs(v):
    queue = deque()
    visit[v] = 1
    queue.append(v)

    while (queue):
        v = queue.popleft()
        print(v, end=' ')
        for i in range(1, n + 1):
            if visit[i] == 0 and adj[v][i] == 1:
                queue.append(i)
                visit[i] = 1

#입력 n : 정점의 개수, m : 간선의 개수, v : 탐색을 시작할 정점의 번호
n, m, v = map(int, input().split())
adj = [[0] * (n + 1) for i in range(n + 1)]
visit = [0 for i in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    adj[x][y] = 1
    adj[y][x] = 1

#출력
dfs(v)
print()

visit = [0 for i in range(n + 1)]
bfs(v)