[Python] DFS/BFS 알고리즘 / 백준 1260 그림 풀이 /

 

개요

 

그래프에서 노드(정점)와 간선으로 표현된다.

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.

두 노드가 간선으로 연결되어 있다면 인접하다. 라고 표현한다.

 

 

 

 

DFS (깊이 우선 탐색)

 

 

그래프에서 깊은 부분을 우선적으로 탐색한다. 

 

 

 

 

BFS 알고리즘 (너비우선탐색)

노드에서 갈 수 있는 모든 노드를 다 방문한다.

말 그대로 너비에서 연결된 모든 곳을 일단 큐에 담는다 

(1) 시작 노드를 큐에 append한 후 방문처리

(2) 큐에서 노드를 POP, 인접 노드 중 방문하지 않은 노드를 모두 큐에 append

(3)  2번 과정을 q가 빌 때까지 반복한다.

 

 

주의사항

from collections import deque
q= deque([v])
q.popleft()

 

q.pop대신 import하여 deque 시간복잡도가 낮은  popleft()를 사용하자 

 

 

 

 

 

 

 

백준 1260 풀이

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

예제 입력 1

 

4 5 1
1 2
1 3
1 4
2 4
3 4

 

예제 출력 1

 

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

 

 

아이디어 생각하기

(1) 입력값 받기

(2) 그래프 선언하기

(3) DFS 함수

(4) BFS 함수

(5) 함수실행

의 순서로 작성할 것이고, 로직을 그림으로 설명하겠다

 

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

 

첫번째 줄 입력

INPUT	N(노드의 수)	M(간선 수)	V(시작지점)
	4 #노드는 1~4번까지 생성	5	1

 

두번째 ~ M+1째줄 입력

M개의 간선으로 이루어진 서로 연결된 노드  input
1	2
1	3
1	4
2	4
3	4

 

 

 

 

그래프 구현

 

그래프를 표로 표현하면 다음과 같다

1과 2가 연결되어있으므로 [1,2] [2,1]  2칸 모두 1로 표시했고,

마찬가지로 다른 연결된 노드가 있는 곳을 모두 1로 채운다. 

 

 

 

 

 

방문 유무를 담는 리스트 visted 선언

visited = [0] * (n + 1)

visted	0	1	2	3	4
	0	0	0	0	0

0 => 아직 방문하지 않음
1 => 방문했음

n+1을 사용하는 이유는

정점은 1~4까지이고,
0번째 인덱스를 사용하지 않기 위해서이다

 

 

 

DFS 탐색 순서도

 

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

 

방문을 했다면 visted는 1이 될 것이고  최종적으로 모두 방문하게 되면 visted = [0,1,1,1,1]가 될 것이다.

vistied	0	1	2	3	4
	0	1	1	1	1

 

방문 순서는 1,2,4,3 

 

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는 공백이 되고 종료된다.

 

 

 

BFS도 마찬가지로 방문을 했다면 visted는 1이 될 것이고, 

최종적으로 모두 방문하게 되면 visted = [0,1,1,1,1]가 될 것이다.

vistied	0	1	2	3	4
	0	1	1	1	1

방문 순서는 1,2,3,4



전체코드

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:
      #방문한다. 재귀함수 활용 
       #호출될 때마다 visted는 1이되고  재귀되어 v에 i가 들어간다
            dfs(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:
                q.append(i) #큐에 추가한다.
                visited2[i] = True
dfs(v)
print()
bfs(v)

 

BFS가 헷갈리니 한 번 더 생각하기

 

(1) q 선언 dequqe를 사용해야 할 것

(2) while문을 돌아 q에 값이 없을 때까지 반복하는 로직 구성

(3) q 맨 앞에 있는 정점을 popleft하고 걔를 기준으로  방문할 수 있는 모든 정점들을 append

즉, 뒤에다 계속 이어붙임.

붙인 정점들 중 가장 앞에 있는 녀석을 꺼내고... 넣고 꺼내고 넣고 반복 

(4) 새로운 노드가 추가되지 않으면, 그 때까지 큐에 남아있는 녀석들을 모두 비우고 함수를 빠져나온다.

 

 

 

 

다시 한 번 주의할 점

 

DFS:  스택과 재귀함수로 구현할 것

BFS: deque, while로 구현, 시간복잡도가 낮은  popleft를 사용하자

graph를 표현할 때 인덱스 0번을 비우고 하면 더 편하다.

 

 

 

★ DFS 알고리즘은 재귀함수를 사용하여 구현하고,

BFS 알고리즘은 while문과 deque를 이용하여 구현하자.