algoqna

22865번: 가장 먼 곳 $N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들이 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할 www.acmicpc.net 1. 친구 A,B,C가 사는 지점을 각 정점의 번호라고 가정 2. 문제의 의도는 친구 A,B,C 각각에 대하여 시작점으로 생각하고 다른 정점까지 방문하는 최단경로 구하기 -> 다익스트라 - 총 3개의 다익스트라 결과값을 가지는 배열을 구한다. 3. 구해진 다익스트라 배열 3개를 각 정점들에 대하여 모두 비교하여 가장 먼 곳의 정점 번호를 찾는다. import java.io.*; import java.util.ArrayList; import ..

- 한 노드에서 다른 노드까지의 최단 경로를 구할 때 사용하는 알고리즘 - 다익스트라의 경우 양수일 때만 작동 가능하다는 점, 벨만 포드는 음수의 가중치가 있을 때 사용하는 것으로 알고 있으면 된다. - 필요한 것은 dist배열 (어떤 지점까지의 최단경로를 저장할 배열) 1) 모든 정점의 개수 -1(V-1)만큼 반복하여 2) 각 정점과 연결되있는 간선들을 파악한다 - 현재 내가 있는 곳이 INF값이 아니고 내가 있는 지점을 거쳐서 다음 지점을 가는 비용이 다음 지점의 비용보다 낮다면 갱신 3) 위의 과정을 딱 1번 더 수행하고, dist의 배열이 변경된다면 음수 사이클이 존재한다는 의미임. - 만약 음수사이클이 존재한다면 기존에 갱신되있는 dist배열이 변경되기 때문. - 정점의 개수 (V번) 반복에 대..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net [문제 조건] 1. 방향성이 없는 그래프 : 무향 그래프 2. 정점의 개수 (1 Y도 갈수 있어야 하며 1 -> N도 갈수 있어야 합니다. * 셋 중 하나라도 만족하지 못한다면 경로가 없다는 뜻입니다. 즉, 1) 1 -> X -> Y -> N : Dijkstra(1,X) + Dijkstra(X, Y) + Dijkstra(Y,N) 2) 1 -> Y -> X -> N : Dijkstra(1,Y) + Dijkstra(Y, ..

어떠한 그래프가 주어지고 임의의 정점 V에서 정점 U로 까지 가는 경로를 탐색한다고 할 때, 1) DFS(깊이 우선 탐색) - Depth First Search 2) BFS(너비 우선탐색) - Breadth First Search 이라고 불리는 두 가지 방법이 있습니다. 모든 정점을 탐색할 때 정점을 탐색한 방문순서를 DFS와 BFS 비교하여 설명하겠습니다. * 이해를 돕기 위해 모든 정점은 '오름차순'의 순서로 방문을 한다고 가정 * 시작 정점은 모두 '1'에서 한다고 가정 1. DFS (깊이 우선 탐색) : 어떤 정점 V와 인접한 정점을 방문하여 방문하지 않은 정점 중, 그 정점이 방문할 수 있는 깊이의 끝까지 간다. 내가 어떠한 정점 V에서 처음으로 U를 방문하여 U로부터 갈 수 있는 최대한의 깊이..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net * N*M의 행렬이 주어지고, (1,1)에서 시작하여 (N,M)까지 도착했을 때의 최단경로를 구하는 문제 1) 이동할 수 있는 곳은 0이고, 이동할 수 없는 곳은 1로 표시되어 있고 이를 벽이라 한다. 2) 단, 벽을 딱 '1번'은 부시고 이동할 수 있다. * N과 M의 크기는 각각 1이상 1000이하 위의 문제는 BFS(너비 우선 탐색)을 이용하여 풀이할 것입니다. 근데, 2) 조건에 의해 1번 부시고 나서의 최단경로도 생각해야 합니다..