기록방

💡 벨만-포드(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..

👉 문제링크🔸 문제 분석 🔸바닷물과 맞닿은 빙하는 1년마다 상하좌우의 바닷물 수 만큼 줄어든다.빙하가 두 덩어리 이상으로 나뉘어지는 최소 시간을 출력한다.끝까지 두 덩어리가 되지 않으면 0을 출력한다.🔸 문제 풀이 🔸빙하가 녹는건 4방탐색을 하면 되고, 덩어리 확인은 그래프 탐색과 4방 탐색을 함꼐 하면 된다.여기서는 그래프 탐색 알고리즘으로 너비 우선 탐색 (BFS) 를 사용했다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque;import java.util.Queue;import java.util.StringTokenizer;public class Main { private static int N, M; private static int..

👉 문제링크 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시 중 M개의 도시를 여행하고자 한다. 경로가 있어서 여행이 가능하면 YES, 불가능하면 NO를 출력한다. 🔸 문제 풀이 🔸 여행 하고자 하는 M개의 도시 간에 경로가 있는지 파악하는 쉬운 방법은 같은 집합에 있는지 확인하는 것이다. 분리 집합(Disjoint Set)으로 N개의 도시들의 집합을 나눈다. 여행 계획상의 도시들이 같은 집합에 있으면 경로가 존재한다는 뜻이다. 분리 집합이 아니라 BFS나 DFS로 Brute F..