[백준] 1260 DFS와 BFS 파이썬 풀이

2021.06.21 - [알고리즘/이론] - [알고리즘] DFS 와 BFS 깊이 우선 탐색, 너비 우선 탐색

[알고리즘] DFS 와 BFS 깊이 우선 탐색, 너비 우선 탐색

 

코드

#N : 정점의 개수/ M: 간선의 개수/ V: 시작할 정점
N,M,V=map(int,input().split())
matrix=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    matrix[a][b]=matrix[b][a]=1 #2차원 배열 간선끼리 연결
visit_list=[0]*(N+1) #왜 정점의 개수 +1?

def dfs(V):
    visit_list[V]=1 #방문한 점 1로 표시
    print(V, end=' ')
    for i in range(1,N+1): #1부터 n까지
        if(visit_list[i]==0 and matrix[V][i]==1):
            dfs(i)

def bfs(V):
    queue=[V] #들려야 할 정점 저장
    visit_list[V]=0 #방문한 점 0으로 표시
    while queue:
        V=queue.pop(0)
        print(V, end=' ')
        for i in range(1, N+1):
            if(visit_list[i]==1 and matrix[V][i]==1):
                queue.append(i)
                visit_list[i]=0

dfs(V)
print()
bfs(V)

풀이

노드의 수+1만큼 2차원 배열을 만든다

그리고 입력받은 것을 저장한다.

N이 4 이면

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

이렇게 리스트가 초기화 될텐데

1과 2가 이어져있으니

matrix[1][2] 와 matrix[2][1]을 1로 바꾸어 둘이가 연결되어있다는 것을 표시한다

예제 입력 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

 

이렇게 생길 것이다

 

dfs보자

1. V 는 1 이니까 visit_list[1]을 1로 바꾼다.

2. for문을 돌면서 1부터 확인한다

3. visit_list[1]이 0이고 (1을 방문하지 않았고) matrix[1][1] (1과 1이 연결되어있는지)

확인한다. -> 아니다

4. for문 다시 시작 (2)

5. 2를 방문안했냐 ? ㅇㅇ 1이랑 2가 이어져있냐? ㅇㅇ

6. dfs(2)를 호출

7. visit_list[2] 를 1로 바꿈

8. for문 시작 i=1 → false ( 1은 이미 방문했음)

/ i=2 → false ( 2는 이미 방문했음)

/ i= 3 → false ( 3은 방문한 기록에 없음 and 2와 3이 인접안했음)

/ i = 4 → true ( 4는 방문한 기록에 없음 and 2와 4가 인접했음)

9. dfs(4)를 호출

10. visit_list[4] 을 1로 바꿈

11.  for문을 돌면서 1 2 까지는 visit에 1 2가 있으니까 패스하고

i=3일때 visit[3]이 0 이고, matrix[4][3]이 1이니까 dfs(3)호출

12. 이제 호출할 수 있는 것 없음

 

1 2 4 3 순서로 호출됨

 

루트 노드의 입장에서 보면 이런 깊이로 이루어져있다

1 2 4까지 갔다가 다시 1로 돌아와서 3을 돌고 그다음은 이미 돌았던 거니까 안감

---

BFS

아까 저 그림으로 이해하자면

너비 우선으로 가야하니까 결국

1 2 3 4 순으로 방문할 것이다

 

1. 큐에 1을 저장한다. (들러야할 것)

2. 여기서는 dfs에서 visit_list가 1이 됐으니까 방문하면 0으로 만든다.

3. 큐에서 맨 앞에 원소를 꺼낸다.

4. 방문하지 않았으면서 인접한 것이 있으면 큐의 맨 뒤에 하나씩 넣고

5. 맨 앞에 원소를 꺼내면서 반복한다.