코드코도

[DFS와 BFS] [Python / C++] 1260. DFS와 BFS - SILVER ⅱ 본문

Boj/DFS, BFS

[DFS와 BFS] [Python / C++] 1260. DFS와 BFS - SILVER ⅱ

고도고도 고도고도 2021. 4. 18. 14:22
728x90

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

 

www.acmicpc.net/problem/1260

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 

 

입력

첫째 줄에 정점의 개수 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) : 너비 우선 탐색

BFS(Breath-Find-Search) 너비 우선 탐색 그래프의 탐색 방법 중 하나의 BFS에 대해서 살펴보려고 한다. BFS는 말 그대로 너비 우선 탐색, 즉 특정 Vertice에서 가장 가까운 Vertice부터 탐색한다는 뜻이다. 우

codekodo.tistory.com

DFS : codekodo.tistory.com/35

 

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

DFS(Depth-Find-Search) 깊이 우선 탐색 지난 시간 BFS에 이어 오늘은 DFS에 대해 알아보려고 한다. DFS는 Depth-Find-Search로 깊이 우선 탐색이다. BFS와 다르게 DFS는 깊이를 우선적으로 탐색한다. 즉 최대 깊..

codekodo.tistory.com

 

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

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

 

 

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

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

 

 

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

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

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

 

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

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

 

728x90
0 Comments
댓글쓰기 폼