[python 파이썬] 백준 1260번 DFS와 BFS

1260번: DFS와 BFS

이문제는 DFS와 BFS를 이용해서 탐색하는 문제이다. 

 

DFS는 깊이탐색, 이어달리기, 한 정점에서 다른 정점 그리고 그 정점에 이어진 정점에 연결하는 느낌

BFS는 너비탐색, 한정점과 이어진 모든 정점을 들른 후에 다음 연결된 정점도 마찬가지로 한다. 

 

DFS에서는 재귀를 사용한다. 

 

 코드는 다음과 같다

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

visit_list=[0]*(n+1)

def dfs(v):

    visit_list[v]=1 # 방문했다는 표시
    print(v,end=' ') # 출력
    for i in range(1,n+1):
        if visit_list[i]==0 and matrix[v][i]==1: #방문하지않은 노드이면서 연결된 노드일때
            dfs(i)


def bfs(v):
    queue=[v] #들려야할 정점 저장
    visit_list[v]=0 #방문한점 0으로 표시 위에서 1로바꿔놔서 여기선 0으로 표기
    while queue:
        v=queue.pop(0) #첫번째 데이터 pop
        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)