deulee의 개발 노트

지금까지 다룬 다익스트라나 벨만-포드 알고리즘들은 모두 한 시작점에서 다른 모든 정점까지의 거리를 구해 주었다. 하지만 한 개의 시작점이 아니라 모든 정점 쌍에 둘 사이의 최단 거리를 구해야 할 때도 있다. 이러한 문제를 해결하는 가장 쉬운 방법은 모든 정점으로부터 다익스트라 알고리즘을 적용하면 되는 것이다. 만약 음수 가중치가 있다면 벨만 포드 알고리즘을 사용하면 된다. 그러나 이것보다 좀 더 빠르고 간단한 방법이 있다. 그것은 이제 설명할 플로이드 워셜(Floyd-Warshall) 알고리즘이다. 플로이드 워셜 알고리즘은 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[][]를 계산한다. 이 배열의 원소 dist[u][v]는 정점 u에서 v로 가는 최단 거리를 나타낸다. 정점의 경유점들 우선..

알고리즘/이론 2023. 6. 28. 23:09

문제 N•M의 모눈종이 위에 아주 얇은 치즈가 다음과 같이 표시되어 있다. 회색 부분은 치즈를 나타내고 흰색 부분은 공기를 나타낸다. 이때 다음처럼 치즈 밖에 있는 공기를 외부 공기, 치즈 안에 있는 공기를 내부 공기라고 할 수 있다. 치즈는 외부 공기에 두 변 이상 만나게 되면 1시간 뒤에 사라진다. 그럼 모든 치즈가 다 녹게 되는데 몇 시간이 걸리게 될까? 이때 모눈정이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M이 주어진다. (5 ≤ N, M ≤ 100) 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 예제 입력 8 9 0 0 0 0 0 0 0 0 0 ..

알고리즘/문제 2023. 6. 4. 22:55

문제 N•M의 행렬로 표현되는 맵이 주어진다. 맵은 0과 1로 이루어져 있으며 '0'은 이동할 수 있는 곳 '1'은 벽을 의미한다. (0, 0)부터 시작하여 (N-1, M-1)의 위치까지 이동하는 최단 거리를 구해야 한다. 이때 상하좌우로 이동할 수 있으며, 벽은 한 개까지 부수며 이동할 수 있다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 1,000) (1 ≤ M ≤ 1,000) 다음 줄에는 N개의 줄에 M개의 숫자가 주어진다. 예제 입력 6 4 0100 1110 1000 0000 0111 0000 예제 출력 15 문제 해결 어디서 힌트를 얻을 수 있을까? '행렬', '최단 경로'를 통해 이 문제가 BFS를 이용하여 문제를 풀 수 있다는 것을 알 수 있다. 우선 최단 경로란 한 번 방문한 노..

알고리즘/문제 2023. 5. 25. 23:14

문제 사이클이 없는 무방향 그래프 트리(tree)가 주어질 때 트리의 지름을 구하는 문제다. 입력 첫째 줄에 노드의 개수 N (1 N; int X, Y, C; int ret; while (1) { if (!(std::cin >> X >> Y >> C)) break ; varr[X].push_back(P(Y, C)); varr[Y].push_back(P(X, C)); } dfs(1, 0); std::memset(cache, 0, sizeof(cache)); maxDis = 0; dfs(maxNode, 0); std::cout

알고리즘/문제 2023. 5. 24. 18:56

문제 정점 N개와 M개의 간선이 주어진다. A번째 정점에서 B번째 정점까지 도달하는 데 드는 최소 비용을 출력하라. 입력 첫째 줄에 N(1 M; for (int i = 0; i > X >> Y >> C; varr[X].push_back(P(Y, C)); } for (int i = 0; i > S >> D; Dijkstra(S); std::cout

알고리즘/문제 2023. 5. 23. 15:19

문제 N개의 정점이 있고 M개의 방향성이 없는 간선과 W개의 방향성이 있는 그래프가 주어진다. 이때 W는 음수의 가중치를 가지고 있다. 어느 시작점이든 출발을 했을 때보다 시간이 더 적은 경우가 있으면 "YES" 없으면 "NO"를 출력하는 문제이다. 입력 첫 번째 줄에는 테스트케이스의 수 T가 주어진다. 두 번째 줄부터 T개의 테스트케이스가 차례로 주어진다. 각 테스트 케이스의 첫 번째 줄에는 정점의 수 N(1 > N >> M >> W; std::vector adj[N]; for (int i = 0; i > X >> Y >> C; adj[X - 1].push_back(P(Y - 1, C)); adj[Y - 1].push_back(P(X - 1..

알고리즘/문제 2023. 5. 23. 14:36

문제 N개의 정점으로 이루어진 그래프 G가 있고, 그래프 G의 모든 간선은 가중치를 2개 가지고 있다. 이 말은 특정 노드 i에서 특정 노드 j로 가는 가중치가 2개 있다는 것이다. 0번 정점에서 1번 정점으로 가는 최단 경로를 찾아야 한다. 경로의 비용은 경로에 있는 간선의 가중치 1을 모두 더한 값인 W1와 가중치 2를 모두 더한 값인 W2를 곱해서 구할 수 있다. 여기서 곱하는 것에 유의하며 문제를 풀어야 한다. 입력 첫째 줄에 정점의 수 N이 주어진다. (2 b.idx) return true; else return false; } return false; } }; std::vector varr[2][21]; int dist[2][21]; int INF = 1e8; int Dijkstra(int S..

알고리즘/문제 2023. 5. 23. 11:13

문제 방향성이 없는 간선이 주어지고 정점 1부터 정점 N까지 도착하는 최단 경로를 구하는 것이다. 이때 정점 X, Y를 경유하는 최단 경로를 구해야 하는 문제이다. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 nDis) { disArr[flag][nNode] = nDis; pqarr.push(std::make_pair(nNode, nDis)); } } } } void init(void) { for (int i = 0; i > N >> M; for (int i = 0; i < M;..

알고리즘/문제 2023. 5. 21. 20:36