그래프4 백준 1240번. 노드사이의 거리 (Java) 1. 문제 조건 2. 아이디어 주어진 예제 입력을 살펴보면 아래와 같다. 인접행렬은 메모리 차지를 많이 할 수 있다고 생각되어 인접리스트로 구현하려고 했다. 또한, 두 노드 사이의 거리를 구하기 위해서는 간선 사이에 양방향 통행이 가능해야 하므로, 부모, 자식 상관 없이(문제에서 부모 자식을 구분할 수도 없었다.) 양 쪽 노드의 자식 노드 list에 노드를 모두 추가해줘야겠다고 생각했다. 이 때, 거리도 함께 기억해야 하므로 class를 생성하여 관리하고자 했다. 문제풀이를 하는 방식은 BFS와 DFS를 떠올렸다. 단순히 하나의 노드에서 목적지 노드까지 간선을 따라 타고 가기만 하면 되는 문제였기 때문이다. 실제로 두가지 방식으로 구현하여 제출 후 정답처리 되었으며 이 문제는 메모리와 시간복잡도 두가지 .. 2024. 2. 16. 플로이드 워셜 알고리즘 1) 개념 - 모든 최단 경로를 구하는 알고리즘 - 다익스트라가 하나의 정점에서 모든 정점까지의 최단거리를 구한다면, 플로이드-워셜 알고리즘은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있다. 다익스트라에 대한 설명은 아래 링크를 통해 확인하자. 2023.07.05 - [Learning-log -CS/Data Structure & Algorithm] - (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교)\ (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교) 1) 개념 한 정점(노드)에서 다른 정점(노드)까지의 최단 경로를 구하는 알고리즘 도착 정점 뿐만 아니라 다른 정점까지 최단경로로 방문하여 각 정점까지의.. 2023. 7. 5. (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교) 1) 개념 한 정점(노드)에서 다른 정점(노드)까지의 최단 경로를 구하는 알고리즘 도착 정점 뿐만 아니라 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾을 수 있음 탐욕기법을 사용한 알고리즘으로 MST 프림 알고리즘과 유사 2) 알고리즘 단계 D : 거리 계산을 위한 배열 U : 경로 배열 출발 노드(a)를 선택 후 a와 연결된 정점들에 대해 배열(D) 값을 가중치로 업데이트한다. >> 다른 정점들은 아직 도달할 수 없는 정점이므로 배열 값 무한대인 상태(배열 초기값을 무한대로 설정해두기)이다. D배열 중 거리가 가장 작으면서 U에 없는 정점(b) 선택한다. a에서 b를 경유해서 갈 수 있는 정점 후보를 보고 그 때 가중치 값을 D에 UPDATE(D[b] +a[b][c])하고 D에 .. 2023. 7. 5. (자료구조 & 알고리즘 정리) 그래프(DFS, BFS) (2023.06.23) 1. 그래프 표현 방식 1) 인접행렬 - 노드의 개수가 N일 때, N*N 행렬(N*N의 2차원 배열)을 만들어 x행과 y행이 연결 되어 있으면 1, 되어 있지 않으면 0을 행렬 값으로 가지도록 표현 - 무방향 그래프 모든 간선이 양 방향으로 이동이 가능한 것이라 간주 x번째 노드와 y번째 노드가 연결되어 있고 그 배열을 adj라 하자 => adj[x][y] = adj[y][x] = 1 행렬은 왼쪽 대각을 기준으로 양쪽이 대칭이 됨 => 대각을 기준으로 양쪽을 모두 사용하지 않고 행 행인 경우 중 하나만 사용해도 됨 - 가중 그래프 행렬의 값을 가중치로 저장 가중치>=0 이라면 간선이 없는 곳의 값을 -1 로 하 - 특징 구현 간단 특정 두 노드가 인접한지 상수시간에 파악 가능 메모리 낭비 심함(정점에 비.. 2023. 6. 23. 이전 1 다음
