[BFS&DFS기본] 백준1260번 (Python)

*DFS(깊이 우선 탐색)

#BFS(너비 우선 탐색)

 

백준 1260. [DFS와 BFS]문제 

 

*DFS: 인접한 노드 중 시작점 V부터 숫자가 작은 노드부터 방문하고, 이미 방문했다면 다시 돌아가 인접 노드를 찾는다.

*BFS:

1) 1번 노드 방문 후 큐에 삽입

2) 가장 앞에 있는 노드1을 pop 후, 인접 노드 2,3,4를 한꺼번에 q에 append

3) 가장 앞에 있는 노드2를 pop 후, 인접 노드 모두 방문처리 했으므로 append하지 않음 

4) 가장 앞에 있는 노드3를 pop 후, 인접 노드 모두 방문처리 했으므로 append하지 않음 

5) 가장 앞에 있는 노드4를 pop 후, 인접 노드 모두 방문처리 했으므로 append하지 않음 

6) q는 공백이 되고 종료. 

 

from collections import deque
#정점, 간선 수, 시작점 입력받음
n, m, v = map(int, input().split())

#초기값을 False로 만들어 그래프 선언
graph = [[False] * (n + 1) for _ in range(n+1)]

#연결된 정점 입력 후 그래프에 채워넣기
for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

#각각 dfs와 bfs 그래프의 방문 여부를 담을 리스트
visited1 = [False] * (n+1)
visited2 = [False] * (n+1)

#dfs알고리즘
def dfs(v):
    visited1[v] = True   #방문 처리
    print(v, end=" ")   #방문 후, 정점 출력
    for i in range(1, n+1):
        if not visited1[i] and graph[v][i] == 1:    #방문기록이 없고, v에 연결되어 있다면
            dfs(i)    #방문(재귀함수)
                      #호출될 때마다 visited는 1이되고 재귀되어 v에 i가 들어간다.

#bfs알고리즘
def bfs(v):
    q = deque([v])  #방문할 곳을 순서대로 넣을 큐 생성
    visited2[v] = True   #방문 처리
    while q:    #큐 안에 데이터가 없을 때까지 실행됨
        v = q.popleft()    #큐 맨 앞에 있는 값을 꺼내서 출력
        print(v, end=" ")
        for i in range(1, n+1):
            if not visited2[i] and graph[v][i] == 1:    #방문기록이 없고, v에 연결되어 있다면
                q.append(i)   #큐에 추가
                visited2[i] = True   #방문 처리

dfs(v)
print()
bfs(v)

 

<정리>

*DFS -> 스택과 재귀함수 사용

*BFS -> deque, while로 구현(시간복잡도가 낮은 popleft사용)

 

 

출처:https://kill-xxx.tistory.com/entry/Python-DFSBFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-1260-%EA%B7%B8%EB%A6%BC-%ED%92%80%EC%9D%B4