[백준] 1260. dfs와 bfs python

🐳 링크

백준 dfs와 bfs

🐕 문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

🐾 풀이 방법

dfs와 bfs로 문제를 해결할 수 있는 가장 기초적인 문제인 것 같다.
방법은 비슷하지만, dfs는 graph의 값이 1인 경우에 자식 노드로 향하기 위해 재귀를 이용하고, bfs는 graph의 값이 1인 경우에는 큐에 삽입하고 또 다른 형제노드에서 1인 값이 있는지 확인한다.

즉, dfs는 더 깊이 bfs는 더 넓게라고 생각하면 좋을 듯.

dfs와 bfs
[그림 출처 : https://namu.wiki]

소스코드

import sys, collections
sys.setrecursionlimit(10 ** 5)
sys.stdin = open("input.txt","rt")

def dfs(x):
    visit[x] = 1
    print(x+1, end=' ')
    for i in range(n):
        if graph[x][i] == 1 and visit[i] == 0 :
            dfs(i)
    return

def bfs(x):
    q = collections.deque()
    q.append(x)

    while q:
        i = q.popleft()
        print(i+1, end= ' ')
        for j in range(n):
            if graph[i][j] == 1 and visit[j] == 0:
                visit[j] = 1
                q.append(j)
    return


n, m, v = map(int, sys.stdin.readline().split())
v -= 1

graph = [[0] * n for _ in range(n)]
for _ in range(m):
    a, b = map(int,sys.stdin.readline().split())
    a, b = a-1, b-1
    graph[a][b] = 1
    graph[b][a] = 1

# dfs
visit = [0] * n
dfs(v)
print()

# bfs
visit = [0] * n
visit[v] = 1
bfs(v)