BOJ / python3 백준 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부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 

1 2 4 3
1 2 3 4

예제 입력 2 

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2 

3 1 2 5 4
3 1 4 2 5

예제 입력 3 

1000 1 1000
999 1000

예제 출력 3 

1000 999
1000 999

 

SOLUTION

 

1. dfs 함수 정의

 

1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다.

     방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 

3) 2)번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

 

False 로 정의되어 있는 visited함수를 True로 바꾸면서 방문처리를 해준다. 

방문처리를 한 노드를 출력해주고 , 

1번 노드를 방문했다면 graph[1] 내부에서 for문을 돌리면서 

아직 1번 노드와 인접한 노드 중 방문하지 않은 노드를 찾아 dfs를 재귀호출 . 

 

이해를 돕기위해 예제 1번을 살펴보자 .

4 5 1

1 2

1 3

1 4

2 4

3 4

처음에는 이 입력을 그대로 graph에 저장하고 dfs를 구현하려 하니 방법이 떠오르지 않아서 입력을 받을 때 

for _ in range(m):
    v1, v2 = (map(int, sys.stdin.readline().split()))
    graph[v1].append(v2)
    graph[v2].append(v1)

for문을 돌면서 

graph[v1]에 v2를 추가 

graph[v2]에 v1를 추가 하는 방식으로 입력을 받게 되면 

graph에 [ [] , [2, 3, 4], [1, 4], [1, 4] , [1, 2, 3]] 와 같이 저장이 된다. 

graph[i]가 의미하는 바는 노드 i 와 인접한 노드들을 의미한다.

 

입력 예시 1에서 시작 노드 1부터 탐색을 시작하면

visited[1] = True : 1번 노드 방문처리

graph[1] = [2, 3, 4]

visited[2] = False 이므로 dfs(graph, 2, visited) 재귀호출.

이를 반복하면 dfs를 통해 모든 노드를 탐색할 수 있다.  

 

2. BFS 함수 정의 

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3) 2)번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

 

queue에 값이 없을 경우 while문 탈출.

queue에 값이 있을 경우 큐의 왼쪽값을 제거하고 값을 v에 저장한 뒤 v출력

for문을 돌면서 v의 인접노드들을 확인하여 아직 방문하지 않은 노드가 있다면 queue에 추가하고 방문처리

graph [ [] , [2, 3, 4], [1, 4], [1, 4] , [1, 2, 3]] 에서 

queue = 1

1 제거하고 출력

for i in graph[1] -> [2,3,4]를 for문으로 검사하면서 방문처리가 되지 않은 2, 3, 4 노드를 queue에 추가하고 방문처리

queue = 2, 3, 4

2 제거하고 출력

3 제거하고 출력

4 제거하고 출력 

 

import sys
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):
    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, start = map(int, sys.stdin.readline().split())
d_visited = [False] * (n+1)
b_visited = [False] * (n+1)
graph = [[] for _ in range(n+1)]

for _ in range(m):
    v1, v2 = (map(int, sys.stdin.readline().split()))
    graph[v1].append(v2)
    graph[v2].append(v1)

for x in graph:
    x.sort()

dfs(graph, start, d_visited)
print()
bfs(graph, start, b_visited)