[백준] 1260번 : DFS와 BFS (파이썬)

문제

나의 답안

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

n,m,v=map(int,input().split())#정점,간선,시작노드
g = [[0] * (n + 1) for i in range(n + 1)] #n+1개의 노드를 가진, 0으로 초기화 된 그래프 생성

for i in range(m):
    x,y=map(int,input().split())
    g[x][y],g[y][x]=1,1

arr_dfs=[0]*(n+1)
arr_bfs=[0]*(n+1)

def dfs(dv):#스택 or 재귀
    arr_dfs[dv]=1
    print(dv,end=' ')

    for i in range(n+1):
        if arr_dfs[i]==0 and g[i][dv]:#해당 노드에 접근한적 있는지, 간선이 있는지
            dfs(i)
            
def bfs(bv):#큐, 큐가 빌 때까지 반복
    arr_bfs[bv]=1
    dq=deque()
    dq.append(bv)

    while dq:
        node=dq.popleft()
        print(node,end=' ')
        for i in range(n+1):
            if arr_bfs[i]==0 and g[i][node]:#해당 노드에 접근한적 있는지, 간선이 있는지
                dq.append(i)#노드 삽입
                arr_bfs[i]=1#방문했다고 표시

dfs(v)
print()
bfs(v)

DFS와 BFS의 기본 구현을 묻는 문제이다.
DFS는 깊이우선탐색으로 모든 노드를 방문하고, 스택이나 재귀함수로 구현한다.
BFS는 너비우선탐색으로 두 노드 사이 최단 경로를 방문하며 큐로 구현한다.