[백준/Python] 1260번 : DFS와 BFS

문제 정보

제목 : DFS와 BFS

번호 : 1260번

사용 언어 : Python

문제 링크

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

1260번: DFS와 BFS

 

시간 제한	메모리 제한
2 초	128 MB

 

문제

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

 

입력

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

 

출력

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

 

입출력 예제

---

나의 풀이

이 문제는 시간 복잡도 그런거 신경 하나도 안쓰고 오로지 개념만 생각하면서 풀었습니다. 다음에 그래프 문제를 풀땐 시간 복잡도를 조금더 신경써서 풀어보겠습니다.

 

첫째 줄에 주어지는 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호를 map함수를 이용해 문자열을 나누어 int형으로 변환후 각각의 변수에 저장합니다.. M의 횟수만큼 반복하는 while루프를 이용하여 그래프를 생성합니다. 간선이 연결하는 두 정점의 번호를 입력받아 map함수를 이용해 int형으로 변환 후 2개의 변수에 저장합니다. 간선은 양방향이기 때문에 각각의 정점에 인접하는 정점을 추가합니다.

이제 DFS와 BFS를 각각 수행합니다.

DFS

stack을 생성하여 탐색을 시작할 정점의 번호를 추가하고 방문한 노드를 추가할 리스트도 생성합니다. 방문할 수 있는 정점이 여러 개일 때 번호가 작은 것 먼저 방문하도록 정렬합니다. stack에 요소가 있는동안 반복하는 while 루프를 생성합니다. stack 요소를 pop()하여 현재의 노드에 저장합니다.  현재의 노드가 방문한 노드 리스트에 없다면 (방문하지 않았다면) 방문한 노드 리스트에 현재의 노드를 추가합니다. for루프를 이용해 인접한 노드를 stack에 추가하는데 방문하지 않은 인접한 노드만 stack에 추가합니다. 모든 반복이 끝나면 방문한 노드 리스트에 하나씩 접근하면서 출력합니다.

BFS

queue를 생성하여 탐색을 시작할 정점의 번호를 추가하고 방문한 노드를 추가할 리스트도 생성합니다. 방문할 수 있는 정점이 여러 개일 때 번호가 작은 것 먼저 방문하도록 정렬합니다. queue에 요소가 있는동안 반복하는 while 루프를 생성합니다. queue 요소를 pop(0)하여 현재의 노드에 저장합니다.  현재의 노드가 방문한 노드 리스트에 없다면 (방문하지 않았다면) 방문한 노드 리스트에 현재의 노드를 추가합니다. for루프를 이용해 인접한 노드를 queue에 추가하는데 방문하지 않은 인접한 노드만 queue에 추가합니다. 모든 반복이 끝나면 방문한 노드 리스트에 하나씩 접근하면서 출력합니다.

 

코드

from collections import defaultdict

graph = defaultdict(list)

N, M, V = map(int,input().split()) # 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V

# 그래프 생성
while(M) :
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)
    M -= 1


# ----- DFS 수행 ----- #
DFS_stack = []
DFS_stack.append(V)
visited_node = [] # 방문한 노드 추가할 리스트

# 방문할 수 있는 정점 여러 개인 경우 정점 번호가 작은 것을 먼저 방문하도록 정렬함
for i in graph :
    graph[i].sort(reverse=True)

while(DFS_stack) :
    current_node = DFS_stack.pop() # 노드 방문
    if (not current_node in visited_node) :
        visited_node.append(current_node)

    # 인접한 노드 stack에 저장
    for neighbor_node in graph[current_node] :
        if (not neighbor_node in visited_node) :
            DFS_stack.append(neighbor_node)

# DFS 출력
for i in visited_node :
    print(i,end=" ")

print()

# ----- BFS 수행 ----- #
BFS_queue = []
BFS_queue.append(V)
visited_node = [] # 방문한 노드 추가할 리스트

# 방문할 수 있는 정점 여러 개인 경우 정점 번호가 작은 것을 먼저 방문하도록 정렬함
for i in graph :
    graph[i].sort()

while(BFS_queue) :
    current_node = BFS_queue.pop(0) # 노드 방문
    if (not current_node in visited_node) :
        visited_node.append(current_node)

    # 인접한 노드 queue에 저장
    for neighbor_node in graph[current_node] :
        if (not neighbor_node in visited_node) :
            BFS_queue.append(neighbor_node)

for i in visited_node :
    print(i,end=" ")