파이썬 / BOJ / 1260번

문제

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

 

입력

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

 

출력

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

 

 

풀이

우선 이 문제는 다른 사람 코드를 보면서 공부하는 식으로 했다.. BFS, DFS 코드에 익숙치 않아서..

대충 코드들을 공부하면서 알게된 점을 정리하면

• BFS => queue, while(무한루프) 사용 // queue의 경우 deque모듈로 사용 가능, 파이썬 내의 queue를 이용하는 것이 좋음
• DFS => stack, 재귀함수 사용
• python에서 list는 자료구조상 stack과 매우 유사
• 컨테이너형 자료를 풀 때는 *이라는 연산자를 변수 앞에 붙이면 쉽게 풀 수 있음
  • 예를 들어 result = [1,2,3] 이걸 print(*result)하게 되면 1 2 3 이렇게 출력되게 할 수 있음
• dict과 set은 탐색순서를 저장하기에는 적절하지 않음 => 순서를 보존하지 않음
• python 3.7부터 dict에서 자료를 집어넣는 순서를 보존하도록 바꿈

n, m, v = map(int, input().split())
matrix = [[0] * (n+1) for _ in range(n+1)] #인접행렬

for _ in range(m):
    link = list(map(int, input().split()))
    matrix[link[0]][link[1]] = 1
    matrix[link[1]][link[0]] = 1

def DFS(current_node, row, foot_prints) :
    foot_prints += [current_node]#지나간 노드
    for search_node in range(len(row[current_node])):
        if row[current_node][search_node] and search_node not in foot_prints: #연결되있고, 지나가지 않은 노드 조건
            DFS(search_node, row, foot_prints) #재귀로 자식노드 탐색
    return foot_prints

def BFS(start):
    queue = [start]
    foot_prints = [start]
    while queue:
        current_node = queue.pop(0) # FIFO, 선입선출
        for search_node in range(len(matrix[current_node])):
            if matrix[current_node][search_node] and search_node not in foot_prints:
                foot_prints += [search_node] #지나간 노드 넣어주기 
                queue += [search_node] #자식 노드 큐에 넣어주기
    return foot_prints
    
print(*DFS(v, matrix,[]))
print(*BFS(v))

 

출처

https://this-programmer.com/entry/%EB%B0%B1%EC%A4%801260%ED%8C%8C%EC%9D%B4%EC%8D%AC-DFS%EC%99%80-BFS