[Baekjoon, Python] 1260번 : DFS와 BFS

도입

백준 단계별 풀기 DFS와 BFS 첫 번째 문제이다.

백준 1260번 문제, 입력, 출력

 

---

백준 1260번 입출력 예제 1, 2, 3

---

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

---

풀이

1. BFS나 DFS를 구현하기 위해서는, 트리나 그래프 구조가 유용하다. 각 노드끼리 연결 되어있다는 것을 표현하는 방식으로 인접행렬을 채택하였다. 

2. DFS는 재귀로, BFS는 큐 자료구조를 사용하여 구현을 하였다. list_visit 배열을 사용하여, 노드의 방문을 기록하였다.

 

---

코드

from sys import stdin

def dfs(V):
    print(V, end=' ')               # 방문한 노드 출력
    list_visit[V] = 1               # 방문한 노드 1체크(나 방문했다!)
    for i in range(1, var_N + 1):   
        if list_visit[i] == 0 and inj_matrix[V][i] == 1:    # 방문하지 않고, 현재 노드에 인접한 노드 방문시 재귀
            dfs(i)      # 재귀

def bfs(V):
    queue = [V]                     # queue에 현재 노드 세팅
    list_visit[V] = 0               # dfs를 돌았기 때문에, 초기화
    while(queue):
        V = queue[0]                # 현재 큐의 노드 세팅
        print(V, end=' ')
        del queue[0]                # queue[0] 삭제
        for i in range(1, var_N + 1):
            if list_visit[i] == 1 and inj_matrix[V][i] == 1: # 방문했고 인접노드 방문했으면 큐에 노드 추가하고 방문 초기화
                queue.append(i)
                list_visit[i] = 0

var_N, var_M, var_V = map(int, stdin.readline().split())
inj_matrix = [[0] * (var_N + 1) for i in range(var_N + 1)]  # 인접행렬 생성 (var_N +1 사이즈 만큼 행과 열)
list_visit = [0 for i in range(var_N + 1)]                  # 방문 정보 리스트 생성 (var_N +1 사이즈 만큼)

for i in range(var_M):  # 인접행렬 세팅   
    x, y = map(int, stdin.readline().split())    # 0 1 1 0 
    inj_matrix[x][y] = 1                	 # 1 0 0 1
    inj_matrix[y][x] = 1               		 # 1 0 0 1
                                       		 # 0 1 1 0
dfs(var_V)
print()
bfs(var_V)

---

마무리

드디어 DFS, BFS문제를 시작한다. 해당 자료구조에 대해서 예전에 공부한 적이 있어서 로직은 어렵지 않았다. 다만, 어떤 문제를 DFS, BFS로 풀어야 하는지 감을 익히는 것이 중요할 것 같다.