[Python][백준/BOJ] 1260번 : DFS와 BFS

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

1260번: DFS와 BFS

 

내 코드

import sys
from collections import deque
input = sys.stdin.readline

n, m , v = map(int, input().split())
board =[[False]*(n+1) for _ in range(n+1)]
visited1 = [False]*(n+1)
visited2= [False]*(n+1)

for i in range(m):
    a, b = map(int, input().split())
    board[a][b] = True
    board[b][a] =True
    
def dfs(v):
    visited1[v] =True
    print(v, end = " ")
    for i in range(1, n+1):
        if not visited1[i] and board[v][i]:
            dfs(i)
            
            
def bfs(v):
    deq = deque([v])
    visited2[v] = True
    
    while deq:
        v = deq.popleft()
        print(v, end=" ")
        for i in range(1, n+1):
            if not visited2[i] and board[v][i]:
                deq.append(i)
                visited2[i]=True
                
            
dfs(v)
print()
bfs(v)

 

DFS, v의 i

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

위의 테스트 케이스에 대해 표를 그려보면 다음과 같다.

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

n은 수의 개수이다. m은 선의 개수라고 보면 되는데, for문을 몇 번 돌릴지라고 생각하면 쉬울 듯하다.

표의 왼쪽을 ~의 라고 생각하면 편한 것 같다.

v라는 변수를 계속 바꿔가면서 끝날 때까지 검사해줄 때,

v = 1 이면 1의 2를 검사하고, 

v = 2 이면 2의 4를 검사하고,

v = 4 이면 4의 3을 검사한다.

그래서 [1, 2, 4, 3] 이 된다. 

 

BFS, v의 i i i i...

queue는 시간복잡도가 O(n)이고, deque는 시간복잡도가 O(1)이라서 deque을 사용했다.

deq = deque([v])

먼저 deque에 v라는 수를 append한다.

그리고 방문했다는 의미로 visited=True로 해준다.

deq이 끝날 때까지 다음과 같은 과정을 반복한다.

1. deq에서 popleft를 통해 이미 들어와 있던 수를 빼낸다.
2. 빼낸 수 출력
3. 그리고 빼낸 수와 이어져 있는 수(하지만 아직 방문하지 않은 수, i)에게 간다.
4. deq에 넣는다.(i)
5. 방문했으니 visited = 1로 만들어준다.

한 놈이 걸리면 죽을 때까지 팬다...이게 bfs인 것 같다........

v 한 놈을 잡고,, 이어져 있는 모든 수를 다 검사한다. 

이때 이어져 있는 수는 i가 된다. 순서대로 i를 집어넣으니 i부터 검사하고, 이후 i와 연결된 수를 검사하러 간다.