[백준] 1260번 DFS와 BFS [Python] - DFS, BFS

 

 

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제

 

문제

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

입력

첫째 줄에 정점의 개수 N$1 ≤ N ≤ 1,000$, 간선의 개수 M$1 ≤ M ≤ 10,000$, 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

https://www.acmicpc.net/problem/1260

 

DFS는 재귀함수로

BFS는 queue로 구현했습니다.

 

import sys

def dfs(S):
    v[S] = True			# 방문 표시
    li.append(S)		# 방문한 노드 저장
    for a in sorted(A[S]):	# 정렬한 순서대로 방문하지 않은 노드에 대해서 재귀호출
        if not v[a]:
            dfs(a)

def bfs(S):
    v[S] = True
    q = [S]
    while q:			# 큐에 원소가 존재하는 동안 반복 -> 방문할 노드가 남은 상태
        node = q.pop(0)
        li.append(node)		# 방문 순서대로 노드 저장
        for a in sorted(A[node]):
            if not v[a]:	# 이전에 방문 안한 노드에 대해서
                v[a] = True	# 방문 표시
                q.append(a)	# 방문하기 위해 노드를 큐에 저장

if __name__ == "__main__":
    N, M, S = map(int, sys.stdin.readline().split())
    A = [[] for _ in range(N + 1)]

    # 그래프를 2차원 리스트로 생성
    # 각 인덱스 번호의 내부 원소(숫자)가 서로 연결됨을 나타냄
    for _ in range(M):
        i, j = map(int, sys.stdin.readline().split())
        A[i].append(j)
        A[j].append(i)
            

    # for a in A:
    #     if a:
    #         a.sort()
    # 주석 처럼 그래프 정보를 담은 A를 미리 다 정렬하고 dfs, bfs 함수에 입력해도 되지만,
    # 이 코드는 내부에서 매번 정렬해서 처리했습니다.
    
    
    # li = 방문한 노드를 순서대로 저장할 리스트
    # v = 방문한 노드 표시할 리스트/ False - 미방문, True - 방문
    li = []
    v = [False] * (N+1)
    dfs(S)
    print(" ".join(map(str, li)))

    li = []
    v = [False] * (N+1)
    bfs(S)
    print(" ".join(map(str, li)))

 

 

예제 입력 1 

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 

1 2 4 3
1 2 3 4

예제 입력 2 

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2 

3 1 2 5 4
3 1 4 2 5

예제 입력 3 

1000 1 1000
999 1000

예제 출력 3 

1000 999
1000 999