[Algorithm] 1260.py DFS/BFS

# https://www.acmicpc.net/problem/1260
from collections import deque

n,m,v=map(int,input().split())
visited=[0] * (n+1)
data=[[0] * (n+1) for i in range (n+1)]
for i in range(m):
    a,b=map(int,input().split())
    data[a][b]=1
    data[b][a]=1

def dfs(v):
    visited[v]=1
    print(v,end=' ')
    for i in range (1,n+1):
        if visited[i]==0 and data[v][i]==1:
            dfs(i)

def bfs(v):
    visited[v]=0
    queue=deque([v])
    while queue:
        v=queue.popleft();
        print(v, end=' ')
        for i in range(1,n+1):
            if visited[i] == 1 and data[v][i] == 1:
                queue.append(i)
                visited[i] = 0


dfs(v)
print()
bfs(v)

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

1 2 4 3
1 2 3 4

DFS

dfs코드 부터 분석해보자.
시작 노드 1 dfs(1)
1 노드는 방문처리하고 print
for문으로 1234노드를 전부 검사한다. 이 중 방문을 안했고 data에 들어가있는 노드를 선택해 재귀적으로 dfs를 불러준다.
그러면 1 -> 2 -> 4 -> 3 이 나온다.

BFS

시작노드 bfs(1)
1 노드는 방문처리하고 1을 큐에 집어넣는다.
큐가 빌때까지 반복문을 돌리는데 1은 popleft에 의해 나오고 print
for문안에서 방문하지 않은 노드 2 3 4 노드를 큐에 차례로 큐에 집어넣는다.
while문에 의해 234가 차례로 나와 print
따라서 1 -> 2 -> 3 -> 4 가 나온다.

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