[백준] 1260번 : DFS와 BFS - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1260번: DFS와 BFS

 

1. 문제 설명

2. 풀이과정

리스트를 만들어 각 정점의 값을 [False]로 설정한 뒤, 탐색한 정점을 True로 바꾸면서 모든 정점의 값이 True가 될 때까지 탐색한다.

DFS는 재귀 알고리즘을 사용하여 계속적으로 정점에 이어진 정점을 탐색하고 탐색할 정점이 없다면 다음 정점으로 넘어가 탐색을 계속한다.

BFS는 deque을 사용하여 정점에서 연결된 모든 정점을 탐색하고 연결된 정점 중 가장 작은 정점으로 넘어가 탐색을 계속한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 라이브러리를 불러온다. import sys
2. BFS 탐색에서 덱(deque) 자료구조 사용을 위해 deque()을 활용한다. 따라서 collections 라이브러리의 deque() 메서드를 불러온다. from collections import deque
3. DFS 함수와 BFS 함수를 생성한다. (함수는 아래에서 자세하게 설명)
4. 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호를 입력받는다. N, M, V = map(int, sys.stdin.readline().split())
5. 각 정점별로 연결된 정점을 저장할 리스트를 만든다. graph = list()
6. 이 리스트는 2차원 배열로 만들어져야 한다. for _ in range(N): graph.append([])
7. 간선의 개수만큼 반복하여 for _ in range(M)
8. 간선의 정보를 입력받는다. v1, v2 = map(int, sys.stdin.readline().split())
9. 입력받은 간선의 정보를 리스트에 저장한다. 여기서 생성한 리스트는 0번부터 인덱스가 시작되므로 입력받은 간선 정보의 정점 번호에서 1 빼준 위치에 1 빼준 값을 추가해줘야 한다. graph[v1 - 1].append(v2 - 1)  graph[v2 - 1].append(v1 - 1)
10. 간선 정보까지 입력된 리스트를 오름차순으로 정렬한다. for i in graph: i.sort()
11. 각 정점별 탐색 결과를 저장할 리스트를 생성하고 False로 초기화한다. result = [False] * N
12. 시작 정점의 인덱스 값을 인수로 한 DFS 탐색을 수행한다. DFS(V - 1)
13. 다음 BFS 출력을 위해 출력되는 줄을 다음 줄로 줄 바꿈 해준다. print()
14. 각 정점별 탐색 결과를 저장할 리스트를 다시 생성하고 False로 초기화한다. result = [False] * N
15. 시작 정점의 인덱스 값을 인수로 한 BFS 탐색을 수행한다. BFS(V - 1)

DFS 탐색 함수

1. 매개변수로 탐색의 시작 정점을 입력받는 DFS 함수를 생성한다. def DFS(start)
2. 탐색 결과 리스트에서 입력받은 시작 정점의 인덱스 위치를 True로 바꿔준다. result[start] = True
3. 시작 정점의 값을 줄 바꿈 없이 공백을 두고 출력한다. print(start + 1, end=' ')
4. 해당 시작 정점과 연결되어 있는 정점들을 순서대로 탐색한다. for i in graph[start]
5. 만약 추출한 인접 정점의 탐색 결과가 아직 False이면 해당 정점을 시작 정점으로 하는 DFS 탐색을 먼저 수행한다. (DFS 깊이 우선 탐색 과정) if (not result[i]): DFS(i)

 

BFS 탐색 함수

1. 매개변수로 탐색의 시작 정점을 입력받는 BFS 함수를 생성한다. def BFS(start)
2. 시작 정점이 원소로 있는 덱(deque)을 생성한다. queue = deque([start])
3. 탐색 결과 리스트에서 입력받은 시작 정점의 인덱스 위치를 True로 바꿔준다. result[start] = True
4. 생성한 deque이 공백이 될 때까지 반복한다. while (queue)
5. deque에서 가장 왼쪽 원소를 추출한다. v = queue.popleft()
6. 추출한 값은 시작 정점과 연결된 정점 중 가장 작은 정점의 인덱스 값이며 해당 정점의 값을 줄 바꿈 없이 공백을 두고 출력한다. print(v + 1, end=' ')
7. 추출한 정점과 연결되어 있는 정점들을 순서대로 탐색한다. for i in graph[v]
8. 만약 추출한 인접 정점의 탐색 결과가 아직 False이면 if (not result[i])
9. 해당 정점의 탐색 결과를 True로 바꾸고 result[i] = True
10. deque에 추가한다. queue.append(i)

반응형

3. 소스코드

import sys
from collections import deque

def DFS(start):
    result[start] = True
    print(start + 1, end=' ')

    for i in graph[start]:
        if (not result[i]):
            DFS(i)

def BFS(start):
    queue = deque([start])
    result[start] = True

    while (queue):
        v = queue.popleft()
        print(v + 1, end=' ')

        for i in graph[v]:
            if (not result[i]):
                result[i] = True
                queue.append(i)

N, M, V = map(int, sys.stdin.readline().split())

graph = list()
for _ in range(N):
    graph.append([])

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

for i in graph:
    i.sort()

result = [False] * N
DFS(V - 1)

print()

result = [False] * N
BFS(V - 1)