[백준] 1260 : DFS와 BFS - Python

문제

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

입력

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

출력

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

import sys
sys.stdin = open("input.text", "rt")
from collections import deque

n,m,v = map(int, input().split()) #노드, 간선
g = [[] for _ in range(n+1)] #1번부터 사용

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

for i in range(1,n+1):
    g[i].sort() #따로 정렬.

ch = [0] * (n+1)

def DFS(v):
    ch[v] = 1
    print(v, end = " ")

    for x in g[v]: #인접 노드
        if ch[x] == 0: #방문 전
            ch[x] = 1
            DFS(x)
    
DFS(v)    
print()
    


ch = [0] * (n+1)
def BFS(v):
    dq = deque()
    dq.append(v) #시작노드 삽입하고 시작
    ch[v] = 1

    while dq:
        now = dq.popleft()
        print(now, end = " ")
        
        for x in g[now]:
            if ch[x] == 0:
                ch[x] = 1
                dq.append(x)

BFS(v)
    

코멘트

이런 유형의 문제가 그래프 전체를 선언하는 것이 아닌(인접행렬로 하는 것이 아닌) 인접 리스트로 푸는 문제이다.

• 입력 예시를 통해 정하면 돼.

처음 아이디어를 짜놓고 문제를 진행하자.
입력값을 받은 이후에

• 그래프 어떤 식으로 ( 인접 리스트, 인접 행렬 )
• dfs 함수 어떻게 짤까?
• bfs 함수 어떻게 짤까?

인접리스트 DFS시에 시작노드 넣고 시작. DFS(V) 그럼 이제 DFS가 돌면서 방문 표시하고 (ch[v] = 1,출력), 인접 노드 돌면서 아직 방문하지 않았다면 그 안에서 다시 DFS하면 된다.

인접리스트 BFS시에는 시작노드를 큐에 넣고 시작, 또한 방문 표시까지 해준 이후에 반복문을 통해 하나씩 꺼낸다. (출력) 그 후에 해당 노드의 인접노드 아직 방문하지 않은 것이 있다면 방문 표시 후 dq에 삽입. 그럼 탐색 끝.