[Python] 백준 1260번 - DFS와 BFS

알고리즘 시간에 다 배운건데 하나도 못짜겠어서 인터넷 보고 공부했다...

 

참고한 사이트 : velog.io/@i-zro/파이썬Python-코테-대비-DFSBFS-백준-1260번-DFS와-BFS

코드도 여기서가져옴!@!!!!!

 

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 #방문한 점 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으로 표시
    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)  #queue에 넣어버림!!!
                visit_list[i]=0

dfs(V)
print()
bfs(V)

[0] * N으로 [0, 0, ..., 0] 을 만들 수 있는지는 몰랐당

 

dfs는 recursive로 짰고 bfs는 iterative로 짰는데

dfs짤때는 visit_list에다가 방문한걸 적어놓고 그 값이 1이면 pass, 0이고 (방문 안했고) 연결된 선이 있으면

그 점에 대해서 dfs를 또 콜해주는 방식으로 했다. 

 

반면 bfs에서는 queue를 만들어서 들려야 할 정점을 저장해줬다. 

제일 처음이라면 첫 정점을 queue에 넣고 queue에 무언가가 들었다면, 제일 먼저 넣은 요소를 pop해서 걔가 방문 안한 노드라면 방문 한걸로 표시하고 걔랑 연결된 노드들 중 안간애들을 다 queue에 넣어버린다.  queue에 아무것도 없을때까지 이걸 계속 반복!