[BOJ] 1260번: DFS와 BFS

문제 풀러 가기 링크!

1260번: DFS와 BFS

DFS와 BFS를 실제로 구현해 볼 수 있는 아주 좋은 문제이다.

DFS는 깊이 우선 탐색이여서 최대한 한 정점에서 최대한 깊게 갔다가 다시 돌아오는 작업을 반복해서 모든 정점을 탐색하는 것이고

BFS는 너비 우선 탐색이여서 층 별로 있는 모든 정점을 다 돌면서 내려간다고 보면 된다.

아직 내가 직접 쓴 글이 없어서 개인적으로 정말 좋다고 생각하는 블로그의 글의 링크를 걸어 놓을테니 이 쪽에 가서 자세히 공부하면 된다.

DFS 설명, BFS 설명

개인적으로 DFS는 재귀함수를 이용하는 것을 좋아해서 원래는 스택을 쓰지만 나는 재귀함수로 구현했고 BFS는 스택을 이용해서 구현했다. BFS는 분리하지 않고 main함수에 적어서 가독성이 떨어질텐데... 그 점은 양해 바랍니다 ㅠ

** 아주 중요한 부분인데 문제에서 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문" 이라고 제시를 했기 때문에 정렬을 시키고 DFS와 BFS를 돌려야 한다. 하지만 테스트 케이스의 문제인지 내가 처음에 제출했을 때 정렬을 하지 않고 냈지만 맞았다.

코드