[DFS와 BFS] [Python / C++] 1260. DFS와 BFS

본 게시글은 PC버전에 최적화 되어있습니다.

 

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

입력

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

출력

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

---

해결 방법

DFS와 BFS의 개념을 묻는 문제이다.

DFS와 BFS에 대해 아직 학습하지 않았다면 좀 더 공부하고 오자.

아래는 내가 정리한 글이다.

 

BFS : codekodo.tistory.com/34

1. BFS(Breath-Find-Search) : 너비 우선 탐색

DFS : codekodo.tistory.com/35

2. DFS(Depth-Find-Search) : 깊이 우선 탐색

 

파이썬으로 구현한 코드이다.

BFS의 경우 파이썬의 extend를 활용했다.

 

 

C++로 구현한 코드이다.

C++로는 조금 색다르게 구현했다.

 

 

정점을 방문할 때 작은 숫자부터 방문하기 위해

파이썬에서는 sort를 활용했는데 C++에서는 이를 사용하지 않기 위해 2차원 배열을 활용했다.

(c++ sort 구현 방법 까먹은건 아님...!)

 

연결된 경우는 1을 저장해서 연결된 상태를 표현했다.

확실히 C++가 번거롭긴 한거 같다...