기록방

👉 문제링크🔸 문제 분석 🔸N개의 도시와 M개의 버스가 주어진다. 1번 도시에서 나머지 도시로 가는 최단 시간을 출력한다.버스는 시작 도시, 도착 도시, 이동 시간으로 이루어져 있다.이동 시간은 정수로 주어진다.🔸 문제 풀이 🔸그래프에서 최단 거리를 구하는 문제이고, 음의 가중치가 있으므로 벨만 포드 알고리즘을 이용한다.N번 마다 M개의 간선을 모두 검사하므로, 시간 복잡도는 O(NM)이다.이동 시간의 최대값은 499 * 10,000 으로, 약 5,000,000 까지 커지므로 int형으로 처리 된다.(노드가 일렬로 연결되어 있고, 에지의 최대 값인 10,000으로만 연결 된 경우)이동 시간의 최소값은 500 * 6,000 * -10,000 으로, -3,000,000,000(-30억) 까지 커지므..

💡 벨만-포드(Bellman-ford)는 그래프에서 음수 가중치 간선이 있을 때 최단 거리를 구하는 알고리즘이다. 다익스트라(Dikjstra), 플로이드-워셜(Floyd-Warshall) 알고리즘과 함께 그래프의 최단 거리를 구하는 방법이다.위 알고리즘들과 다르게 음수 가중치의 간선이 있어도 최단 경로를 구할 수 있다.단, 음수 사이클이 있을 경우 최단 거리를 구할 수 없으므로 예외 처리가 필요하다. (음수 사이클의 존재 여부를 파악할 수 있다).매번 모든 간선을 확인하기 때문에 시간 복잡도는 O(VE) = Vertex * Edge로 다익스트라보다 느리다. 🚀 벨만-포드 알고리즘 동작 과정출발노드, 도착노드, 가중치 3개의 변수를 갖은 Edge클래스(혹은 배열)를 선언한다.계산 결과인 최단경로를 저장..

👉 문제링크🔸 문제 분석 🔸N*M 미로에서 (1, 1) 부터 (N, M) 까지 가는 최소 비용을 구하는 문제이다.미로는 빈 방과 벽으로 이루어져 있고, 벽을 부수는데 비용이 1 소모된다.🔸 문제 풀이 🔸가중치가 0과 1로 이루어진 그래프에서 최소 비용 혹은 최단 경로를 구하는 문제라고 볼 수 있다.최단 경로 문제는 다익스트라(Dijkstra) 알고리즘을 많이 사용한다. 첫 번째 풀이에서 사용했다.다익스트라의 시간 복잡도는 O(E log V) 이다.노드를 방문해 가며, 가중치가 더 적은 경로가 발견되면 해당 노드부터 다시 경로를 탐색해보는 방법이다.가중치가 0과 1로 이루어진 경우에 0-1 BFS를 사용해서 더 효율적으로 풀이할 수 있다.0-1 BFS의 시간 복잡도는 O(V + E) 이다.모든 노..

💡 0-1 BFS는 특정 상황의 그래프에서 최단 경로를 찾을 때 사용된다. 가중치가 0과 1로 이루어진 그래프에서 최단 경로를 찾을 때 사용한다.최단 경로를 구할 때 많이 사용하는 우선순위 큐 다익스트라(Dikjstra) 알고리즘은 시간 복잡도가 O(E log V)인 반면에, 0-1 BFS는 일반적인 BFS 시간 복잡도와 같이 O(V + E)의 선형 시간 복잡도를 갖는다.일반 BFS 에서 큐를 사용하는 것과 달리 덱(Deque)을 사용한다. 🚀 0-1 BFS의 동작 과정덱의 front에서 현재 방문한 노드를 꺼낸다.연결된 인접 노드를 살펴본다.(현재 비용+ 다음 노드 가중치) 다음 노드에 기록된 비용을 갱신해 준다.노드가 갱신될 때, 가중치가 0이라면 덱의 front, 가중치가 1이라면 덱의 back..

👉 문제링크🔸 문제 분석 🔸N개의 컴퓨터 사이 M개의 네트워크가 있다.모든 컴퓨터를 연결할 수 있는 네트워크 최소 비용을 구한다.🔸 문제 풀이 🔸전형적인 MST 문제이다. 모든 노드를 한 번씩은 연결하며 최소 비용이 되도록 하기 때문이다.여기서는 크루스칼(Kruskal) 알고리즘을 사용했다.🔸 코드 🔸import java.io.*;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { private static int[] parent; public static void main(String[] args) throws IOException { // Input Buf..