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

n, m, v = map(int, input().split())

g = [[0] * (n+1) for i in range(n+1)]

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

visit = [0] * (n+1)

def dfs(v):
    visit[v] = 1 # 방문한 점 1
    print(v, end=" ")
    for i in range(1, n+1):
        if (visit[i]==0) and (g[v][i]==1):
            dfs(i)

def bfs(v):
    q = [v]
    visit[v] = 0 # 방문한 점 0
    while q:
        v = q.pop(0)
        print(v, end=" ")
        for i in range(1, n+1):
            if (visit[i]==1) and (g[v][i]==1):
                q.append(i)
                visit[i] = 0

dfs(v)
print()
bfs(v)

 

간선의 개수만큼 for문으로 a, b를 입력받아서 2차원 배열을 만들어 연결된 부분을 1로 만들어 준다

g = [[0]*(n+1) for i in range(n+1)] 인접 역행렬 만들어주기

방문한 정점을 알기 위해 visit으로 1차원 배열을 만들어 주고 시작

BFS는 큐를 사용해 큐 안에 데이터가 없을 때까지 반복시켜 주고 DFS는 재귀호출을 통해 방문하지 않았다면 함수를 실행시켜 준다