깊이우선탐색2 깊이우선탐색과 너비우선탐색 문제 그래프가 주어질 때, 0번 정점을 시작으로 하여 깊이우선탐색과 너비우선탐색의 결과를 출력하는 프로그램을 작성하시오. 단, 노드를 방문할 때는 노드 번호가 작은 순서대로 방문한다고 하자. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다. 정점의 번호는 0번부터 N-1번까지이다. 출력 첫 번째 줄에 깊이우선탐색 결과, 두 번째 줄에 너비우선탐색 결과를 출력한다. 예제 입력 9 12 0 1 0 2 0 3 1 5 2 5 3 4 4 5 5 6 5 7 5 8 6 7 7 8 예제 출력 0 1 5 2.. 2022. 8. 17. DFS(깊이 우선탐색) 깊이 우선탐색이란? 그래프를 탐색할 때 쓰이는 알고리즘 특정한 노드에서 가장 멀리 있는 노드를 먼저 탐색하는 알고리즘 주어진 맵전체를 탐색하며 한번 방문한 노드는 다시 방문하지 않는다. // 수도코드 DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v) 어떠한 정점 u의 visited를 참으로 바꾸고 u로부터 연결되어 있는 v지점을 탐색한다. 방문되어 있지 않은 노드에 대해 재귀적으로 DFS를 호출. 1번 노드에서 시작하여 4번노드까지 가장 멀리 떨어져있는 정점까지 방문한 다음 그 다음 정점들을 차례로 방문한다. DFS 구현방법 - 1 void dfs(int here){ visited[here] = 1; for(in.. 2022. 6. 24. 이전 1 다음
