728x90 반응형 bfs2 백준 24444 - 너비 우선 탐색 1( Python) - BFS https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 너비 우선 탐색은 queue 자료구조를 사용해서 풀 수 있다. 기본예제와 차이점 정리 1. 양방향간선이므로 그래프를 뒤집어서 한 번 더 저장해야됨 2. 오름차순으로 방문해야하므로 큐에서 꺼낸 노드의 그래프를 순회하기전에 해당 그래프를 정렬해주어야한다. 3. 방문한 순서대로 출력을 해야하는 것이 아닌 해당 노드의 방문 순서를.. 2023. 1. 18. 탐색 알고리즘 - DFS / BFS Tip 탐색문제는 그래프 형태로 표현 후 풀이하면 좋다. DFS : Depth-First Search, 깊이 우선 탐색 인접 행렬 방식 : 2차원 배열에 각 노드가 연결된 형태를 기록 연결되지 않은 노드는 무한의 비용이라고 작성 장점 : 모든 관계를 저장하므로 메모리가 불필요하게 낭비된다. 단점 : 인접 리스트 방식에 비해 속도가 빠르다 인접 리스트 방식 : 모든 노드에 연결된 노드에 대한 정보를 차례로 연결하여 저장 장점 : 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 단점 : 연결된 데이터를 하나씩 확인해야하므로 속도가 느리다. def dfs(graph, v, visited): visited[v] = True #현재 노드 방문 처리 print(v, end=' ') for i in g.. 2022. 9. 26. 이전 1 다음 728x90 반응형
