[백준 / Python] 1260번 DFS와 BFS | 초코더

 

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

1260번: DFS와 BFS

 

접근법

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))