[백준 1260 DFS와 BFS] PYTHON

 

bfs랑 dfs를 둘다 사용해보는 문제다.

bfs의 경우 너비 우선 탐색이라 시작 노드에 연결된 모든 노드를 탐색한 후 

맨 앞의 노드를 기준으로 또 탐색하는 방식이다.

 

bfs의 경우 깊이 우선 탐색으로 시작 노드에 연결된 맨 앞의 노드를 찾고

그 앞의 노드와 연결된 맨 앞의 노드를 탐색하는 방식이다.

 

def dfs(V):
    visit_list[V]=1
    print(V,end=' ')
    for i in range(1,N+1):
        if(matrix[V][i]==1 and visit_list[i]==0):
            dfs(i)
            
def bfs(V):
    Q=[V]
    visit_list[V]=0
    while(Q):
        V=Q.pop(0)
        print(V,end=' ')
        for i in range(N+1):
            if(visit_list[i]==1 and matrix[V][i]==1):
                Q.append(i)
                visit_list[i]=0
    
if __name__ == "__main__":
    N,E,V=map(int,input().split())
    matrix=[[0]*(N+1) for i in range(N+1)]
    for i in range(E):
        a,b=map(int,input().split())
        matrix[a][b]=matrix[b][a]=1
    visit_list=[0]*(N+1)
    dfs(V)
    print()
    bfs(V)