[C++] 백준 1260번 DFS와 BFS

오랜만에 풀어보는 DFS와 BFS 문제였다. 그래프 이론을 알고 있다면 어려운 문제는 아니다.

 

DFS란?

깊이 우선 탐색(Depth First Search)라는 그래프 탐색 방법 중 하나로, 방문해 나갈 수 있는 정점이 있다면 계속해서 탐색하는 것. 시작점이 루트가 되어서 깊이를 1씩 더해가는 방식이다. 보통은 재귀함수를 이용해서 구현한다. BFS의 시간복잡도는 n개의 정점과 m개의 간선이 있을 때, O(n + m)이다. 백트래킹(backtracking) 알고리즘이 DFS에서 파생됐다.

BFS란?

너비 우선 탐색(Breadth First Search)라는 그래프 탐색 방법 중 하나로, 이번에 방문한 정점에서 방문해 나갈 수 있는 모든 정점을 모두 탐색하는 것을 의미한다. 보통은 자료구조 queue를 이용해서 구현을 많이 한다. BFS에서 찾는 경로는 최단 경로(최소의 간선)이다. BFS의 시간복잡도는 n개의 정점과 m개의 간선이 있을 때, O(n + m)이다. 다익스트라(dijkstra) 알고리즘도 BFS에서 파생됐다.

 

처음 이 문제를 봤을 때

우선은 DFS와 BFS를 오랜만에 봐서 문제의 첫번째 테스트 케이스로 그림을 그렸다.

이 테스트 케이스를 그리고 감이 다시 살았고, 문제에서 유의점을 읽어보았다.

1. 그래프는 여러 개의 간선이 가능하다는 조건 -> flag 배열을 만들어서 이미 방문한 곳인지 확인하면 해결 가능.
2. 양방향 그래프 -> 간선을 추가할 때, 두 개의 정점에서 모두 양쪽 정점으로 이동할 수 있게 그래프 만들기.
3. 숫자가 작은 점부터 방문 -> 사실 이 부분이 헷갈렸는데, 다익스트라 알고리즘을 풀면서 작은 점부터 방문하는 것이 큐가 아니라 우선순위 큐를 쓴다고 해석했는데, 테스트 케이스와 다르게 나왔다. (사실 그래프 이론을 안다면 당연히 우선순위 큐는 생각할 필요가 없다.)

 

문제풀이

사용한 STL과 변수

우선 STL에서는 그래프 구현을 위한 vector, BFS 구현을 위한 queue, 정렬을 사용하기 위해 algorithm을 사용했다.

변수에는 입력받는 변수 3개와 그래프를 나타내기 위한 vector 변수가 있다.

[C++] 벡터 사용 시, () 선언과 [] 선언의 차이

이 때 벡터의 ()선언과, []선언이 헷갈려서 정리를 해놨다.

 

그리고 DFS와 BFS를 할 때, 이미 방문한 곳인지 확인하는 bool 배열도 만들었다.

 

DFS 알고리즘. 재귀함수로 구현했다.

DFS 알고리즘이다. 어려운 부분은 없고, DFS 메서드에 들어오면

1. 해당 번호를 출력
2. 방문한 정점임을 기록한다.
3. 해당 정점이 방문할 수 있는 정점들 중에서 방문하지 않은 정점으로 진입한다.

의 순서로 이루어져 있다.

 

BFS 알고리즘. 큐 자료구조를 이용했다.

BFS 알고리즘은 큐를 이용해서 구현했다. BFS는 다음과 같은 순서로 이루어진다.

1. 큐를 선언하고 매개변수로 받은 시작점을 큐에 삽입한다. 이 때, 정점을 방문했다고 기록을 반복문 진입 전에 남긴다.
2. 큐가 빌 때까지, 즉 더 이상 방문할 수 있는 정점이 없을 때 까지 반복문을 실행하고, 큐의 맨 앞 부분을 현재 정점으로 선언한 후 출력한다.
3. 현재 정점에서 방문할 수 있는 정점들 중에서 방문하지 않은 정점을 큐에 삽입해둔다.

메인함수

입력받은 후에, 각 정점들의 인접 리스트들을 오름차순으로 정렬하기 위해 sort알고리즘을 사용했다.

후에 dfs와 bfs를 호출해서 문제를 해결했다.

 

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인 가능하다.