dfs

[C++] 백준 1167번 트리의 지름

[C++] 백준 1967번 트리의 지름 그래프 탐색 문제. 처음에 그냥 정점마다 DFS를 모두 돌려서 제출했는데 맞췄다. (시간 복잡도를 계산해도 가능할 것 같았다.) 그런데 문제가 의도하는 바가 이것도 아닌 것 같고, 제출 내역에 다 kimyunseok.tistory.com 위 문제와 거의 똑같은 문제. 차이점이라면, 루트 노드가 1이 아니다. 정점 번호가 작은 순서부터 입력되는 것이 아니라 랜덤으로 입력된다. -1이 나오기 전까지 노드를 연결시킨다. 정도가 되겠다. 3번 차이점은 사실 크게 중요하지는 않다. 위에 링크를 남긴 문제를 풀었다면 이 문제도 아마 크게 어렵지 않게 풀 수 있다. 문제풀이 자세한 풀이는 생략하겠다. (위 비슷한 문제와 거의 똑같은 방식으로 풀었다.) 우선, 루트 노드가 무엇인..

[C++] 백준 1967번 트리의 지름

그래프 탐색 문제. 처음에 그냥 정점마다 DFS를 모두 돌려서 제출했는데 맞췄다. (시간 복잡도를 계산해도 가능할 것 같았다.) 그런데 문제가 의도하는 바가 이것도 아닌 것 같고, 제출 내역에 다른 사람들 시간을 보니 다시 풀어야 겠다고 생각해서 다시 풀어서 제대로 맞출 수 있었다. DFS를 자유자재로 변형할 수 있으면 쉽게 맞출 수 있는 문제였다고 생각한다. 문제풀이 우선 처음 이 문제를 풀었을 때, 정점의 개수가 최대 10,000개인 것을 확인했고 간선의 개수가 최대 9,999개인 것을 확인했다. 각 정점마다 DFS를 한 번 하는데 소요되는 시간은 모든 정점을 방문했을 때, O(N)의 시간이 소요된다. 그러면 모든 정점에서 DFS를 한다면 총 소요되는 시간은 O(N^2)이다. N은 최대 10,000이..

[C++] 백준 2667번 단지번호붙이기

그래프 이론 문제. 연결 요소(Connected Components)의 개수를 구하고 각 연결 요소에서의 정점의 개수를 오름차순으로 정렬해서 출력하는 문제. 연결 요소의 개수는 DFS, BFS로 구할 수 있다. 나는 DFS를 이용해서 해당 문제를 풀었다. 문제풀이 먼저 입력받는 정수 n, 그리고 지도를 나타내는 2차원 배열 map(1~25의 idx를 사용하기 위해 26의 크기로 만들었다.) 각 연결요소마다 집이 몇 개가 있는지 세기 위해 house_count라는 정수형 변수를 만들었다. 그리고 해당 정점이 이전에 방문했는지 체크하기 위한 bool형 2차원 배열 visit을 만들었다. house_vec 벡터형 변수로 각 연결요소에서 정점의 개수들을 입력해서 저장했다. DFS 메서드이다. 사실 이 부분에서 ..

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

오랜만에 풀어보는 DFS와 BFS 문제였다. 그래프 이론을 알고 있다면 어려운 문제는 아니다. DFS란? 깊이 우선 탐색(Depth First Search)라는 그래프 탐색 방법 중 하나로, 방문해 나갈 수 있는 정점이 있다면 계속해서 탐색하는 것. 시작점이 루트가 되어서 깊이를 1씩 더해가는 방식이다. 보통은 재귀함수를 이용해서 구현한다. BFS의 시간복잡도는 n개의 정점과 m개의 간선이 있을 때, O(n + m)이다. 백트래킹(backtracking) 알고리즘이 DFS에서 파생됐다. BFS란? 너비 우선 탐색(Breadth First Search)라는 그래프 탐색 방법 중 하나로, 이번에 방문한 정점에서 방문해 나갈 수 있는 모든 정점을 모두 탐색하는 것을 의미한다. 보통은 자료구조 queue를 이용..