1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
핵심요소
- DFS와 BFS의 정지 요건을 어떤식으로 지정해야 하는가?
- 인접행렬을 어떠한 방식으로 구현해야 하는가?
문제풀이
그래프를 표현하는 대표적인 방법인 인접 행렬을 구성하여 문제를 풀어야할 것 같다.
각 간선간의 이동 방향이 지정되지 않은 무방향 그래프 이므로 인접 행렬이 대칭으로 구현된다.
이제는 문제를 구현해보자.
DFS > BFS 순으로 정답을 도출해내야 하기 때문에 DFS에서는 방문한 List를 저장하고
BFS에서는 방문한 List 순서대로 추출해내도록 설정한다.
그러면 DFS와 BFS의 정지조건에 대해서 어떻게 정의 해야 할까?
DFS 에서는 방문하지 않았고 해당하는 위치로 이동할 수있는 간선이 존재하였을 경우 방문을 하도록 하자.
그렇다면 BFS는 어떻게 정의해야할까?
문제의 조건 중 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것 먼저 방문하고," 가 있다.
그러므로 현재의 해당하는 위치에서 이동가능한 간선을 큐 형식으로 저장해 순서대로 이동해야겠다.
제어문 조건은 DFS에서 방문 했었던 List항목을 1로 변경하였다.
그러므로 방문한 List의 값이 1일 경우 방문한 적이 없으므로, 제어문에서도 수정하도록 하자.
코드의 핵심적인 작업이 끝났다.
이제는 기본적인 입력과 출력부분을 수정하여 코드를 완성하도록 하자.
'항해99 > 알고리즘 마라톤' 카테고리의 다른 글
| 항해99 알고리즘 마라톤 30번 문제 [백준 1021번] (0) | 2021.06.23 |
|---|---|
| 항해99 알고리즘 마라톤 21번 문제 [백준 2805번] (0) | 2021.06.23 |
| 항해99 알고리즘 마라톤 14번 문제 [백준 2869번] (0) | 2021.06.23 |
| 항해99 알고리즘 마라톤 13번 문제 [백준 1436번] (0) | 2021.06.23 |
| 항해99 알고리즘 마라톤 11번 문제 [백준 1011번] (0) | 2021.06.16 |
