[백준 / Python] 1260번 DFS와 BFS | 초코더
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
www.acmicpc.net
접근법
DFS와 BFS는 개인적으로 복잡하다고 느낀 코드이기 때문에 코드를 나누어서 세세히 설명해보겠습니다.
입력은 예제 입력1인 4 5 1 을 예로 들겠습니다.
1 2
1 3
1 4
2 4
3 4
1. N,M,V를 받아오고 '0'으로 이루어진 인접행렬 (N+1)*(N+1) 짜리 생성
N, M, V = map(int, input().split())
matrix = [[0] * (N + 1) for _ in range(N + 1)]
2. for문을 간선의 개수만큼 반복하여 간선에 해당하는 정점에는 1로 바꿔주는 작업. 여기까지가 인접행렬을
만들어주는 단계입니다. 현재 노드의 상황은 [0][0][0][0][0]
[0][0][1][1][1]
[0][1][0][0][1]
[0][1][0][0][1]
[0][1][1][1][0]
for _ in range(M):
link = list(map(int, input().split()))
matrix[link[0]][link[1]] = 1
matrix[link[1]][link[0]] = 1
3. dfs코드(깊이 우선 탐색)
- foot_prints는 말그대로 발자취입니다. 노드가 움직여다니는 자취를 저장해주는 변수입니다.
- 가장 처음에는 foot_prints에 current_node인 1을 저장합니다.
- for문을 돌리게 되는데, row[current_node]는 row[1]로 row(=matrix)의 첫번째열의 행을 의미합니다.
첫번째열의 길이만큼 즉, 5번 반복합니다. search_node에는 0부터 4까지 들어갑니다.
- 우선 반복문에서 and가 나왔는데 두 조건 다 만족해야 합니다. row[1][0] 는 '0'이기 때문에 이미 FALSE입니다.
- 다시 올라가서 search_node가 1이면 row[1][1] 은 '0', 다시 올라가서 search_node가 2이면 row[1][2]는 '1'
- 그럼 search_node가 foot_prints안에 없는지 보겠습니다. foot_prints에는 현재 current_node만 추가
되어있으므로 이 또한 True입니다.
- 이제 foot_prints에 dfs(2,row,foot_prints)를 호출. 즉 재귀형식입니다. 그렇다면 이제 current_node가 2인 채로
아까의 단계를 반복해나갑니다.
- foot_prints에는 2가 담겨서 [1,2]의 형태를 갖춥니다.
def dfs(current_node, row, foot_prints):
foot_prints += [current_node]
for search_node in range(len(row[current_node])):
if row[current_node][search_node] and search_node not in foot_prints:
foot_prints = dfs(search_node, row, foot_prints)
return foot_prints
4. bfs코드(넓이 우선 탐색)
- queue와 foot_prints에는 시작노드를 담아둡니다. 여기서는 1이 들어갑니다.
- while queue: 는 queue안에 원소들이 없어질 때까지 반복합니다.
- current_node 변수에 queue의 가장 첫번째 원소를 꺼내옵니다.(=1)
- for문을 matrix[1]의 길이만큼(=5) 돌립니다.
- dfs와 동일하게 matrix[1][0], matrix[1][1]은 FALSE이므로 넘어가겠습니다.
- matrix[1][2] and 2가 foot_prints에 없으므로, foot_prints와 queue에 [2]추가. -> 이와 같은 방법으로 [3]과 [4]추가
- 그리고 while문을 다시 반복했을 때 if문의 두번째 조건인 search_node가 foot_prints에 없냐는 조건에서 모두
FALSE가 되므로 return foot_prints를 해주면 됩니다.
def bfs(start):
queue = [start]
foot_prints = [start]
while queue:
current_node = queue.pop(0)
for search_node in range(len(matrix[current_node])):
if matrix[current_node][search_node] and search_node not in foot_prints:
foot_prints += [search_node]
queue += [search_node]
return foot_prints
나의풀이
N, M, V = map(int, input().split())
matrix = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
link = list(map(int, input().split()))
matrix[link[0]][link[1]] = 1
matrix[link[1]][link[0]] = 1
def dfs(current_node, row, foot_prints):
foot_prints += [current_node]
for search_node in range(len(row[current_node])):
if row[current_node][search_node] and search_node not in foot_prints:
foot_prints = dfs(search_node, row, foot_prints)
return foot_prints
def bfs(start):
queue = [start]
foot_prints = [start]
while queue:
current_node = queue.pop(0)
for search_node in range(len(matrix[current_node])):
if matrix[current_node][search_node] and search_node not in foot_prints:
foot_prints += [search_node]
queue += [search_node]
return foot_prints
print(*dfs(V, matrix, []))
print(*bfs(V))