BOJ 문제풀이 썸네일형 리스트형 백준 10282 : 해킹 https://www.acmicpc.net/problem/10282 어떤 컴퓨터x 가 동시에 a,b,c 3대의 컴퓨터를 의존한다고 했을 때 그 컴퓨터x 는 a 또는 b, c 에 의해 감염될 수 있다. 근데 이때 a,b,c 중 가장 감염이 빠른 컴퓨터 기준 걸린 시간 + s 만큼 컴퓨터x 가 감염이 되므로 결국 최단경로를 찾는다익스트라 알고리즘이다. 최소 경로를 갱신할 때 만약 이전 dist값이 INF이면 처음 감염된 컴퓨터이므로 count값을 ++ 시켜주는 것으로 감염된컴퓨터의 총 개수를 구할 수 있고 INF가 아닌 컴퓨터들의 dist중 max값이 가장 마지막 컴퓨터가 감염완료된 시점으로볼 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2.. 더보기 백준 10473 : 인간 대포 https://www.acmicpc.net/problem/10473 한 정해진 출발지점에서 특정 도착지점으로 가는 최단 경로이자 각 노드마다 가중치(시간)가 다르므로 다익스트라로구현할 수 있다. 단 간선이 미리 주어져있지는 않아서 n^2 연산을 통해 모든 정점들을 다 연결하고조건에 따라 1. 대포를 타고 이동할 것인지(거리가 30m 이상이면 대포를 타는 것이 낫다.)2. 걸어서 이동할 것인지 계산해 가중치를 설정해주었다. 이 때 대포를 타든 걸어서 가든 정점과 정점을 사이를 이동할때는일직선으로 이동한다고 가정한다(최소시간) 이렇게 각 정점과 연결된 간선에 대한 설정을 마치면 다익스트라로 최단경로를 구할 수 있다.나는 vertex[1]을 시작지점, vertex[2]를 도착지점으로 설정해주고 시작하였다. 그.. 더보기 백준 1238 : 파티 https://www.acmicpc.net/problem/1238 단방향 도로이고 목적지 까지 가는 것 뿐 만 아니라 돌아가는 것 까지 계산해야한다는 것이 특징이다. 파티마을로 부터 각각의 마을로 돌아가는것은 파티마을을 시작지점으로 한 다익스트라 한번으로 모두 구할 수 있다. 문제는 각자의 마을에서 파티마을로 가는 최단경로를 구하는 것이다. 1. 각자의 마을을 기준으로 파티마을까지 다익스트라를 N-1번 해준다. - 처음에 이처럼 풀었는데 216ms 로 AC받긴 했다.- 그러나 역시 N-1 번 다익스트라를 한다는 것은 매우 비효율적이다. 2. 단방향의 경로를 역으로 설정해 파티마을을 기준으로 다익스트라 한다. - 이것이 훨씬 나은 해결방법이다. 이 경우 총 다익스트라 2번으로 각 마을에서의 왕복시간을 모두.. 더보기 백준 4485 : 녹색 옷 입은 애가 젤다지? https://www.acmicpc.net/problem/4485 전형적인 다익스트라 알고리즘 문제이다.한 지점을 기준으로 특정 지점까지 최단경로를 구하고 양수인 가중치가 주어질 때 다익스트라를 활용할 수 있다. 각 점을 기준으로 상,하,좌,우가 연결되있고 priority_queue에 최단경로를 갱신하면서 넣어주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53#include #include #define MAX 126 #define INF 1000000000 using names.. 더보기 백준 2211 : 네트워크 복구 https://www.acmicpc.net/problem/2211 처음에 최소스패닝트리(MST) 문제인지 헷갈려서 삽질을 했다. 그러나 위의 (2)번 조건에 의해 결국 다익스트라로 해결해야 한다.모든 컴퓨터들이 1번 슈퍼컴퓨터와의 최소경로를 만족해야한다. 따라서 1번을 기준으로 다익스트라를 해주고 각 컴퓨터들에 저장된 이전 정점 정보를 가져와 연결하면 된다. Com 구조체에 현재 거리 뿐만 아니라 이전 정점의 정보까지 저장해야 한다.struct com{int idx, dist = INF, post = 0;}; 다익스트라를 돌면서 최소 거리를 갱신해줄 때 post값도 갱신해주면 된다.for(현재 정점과 연결된 모든정점 탐색){if(다음 정점의 거리 > 현재정점까지 거리 + 간선의 가중치){//최소거리 갱신.. 더보기 백준 1504 : 특정한 최단 경로 https://www.acmicpc.net/problem/1504 다익스트라 알고리즘인데 조건이 추가되었다. 바로 주어진 두 정점을 반드시 거쳐가야하는 것이다.시작점을 1, 두 정점을 n1, n2, 끝점을 n 이라고 한다면 1-->n1-->n2-->n또는1-->n2-->n1-->n 루트의 두가지 방법이 있다. 각각 --> 과정에서는 다익스트라로 최소의 경로로 진행한다.지나온 길을 다시 거쳐갈 수 있기때문에 각각 다익스트라로 최소비용을 구한다음 합쳐주는 것이가장 짧은 루트이다. 이 때 총 세 번의 다익스트라로 모든 루트를 구할 수 있다. 1. 1-->n1, 1-->n2 2. n1-->n23. n-->n1, n-->n2 를 구한다음 2개의 경로중에 더 작은 것을 선택해주면 됨. 1 2 3 4 5 6 7 8 .. 더보기 백준 1916 : 최소비용 구하기 https://www.acmicpc.net/problem/1916 역시 최단경로 기본문제이다.한 점에서 다른 점으로 도달하는데 가중치가 있고 최소비용을 구해야 한다면 Dijkstra를 고려하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51#include #include #include #define MAX 1001 #define INF 1000000000 using namespace std; int n, m, init, target; struct City{ int idx, dist = INF; .. 더보기 백준 1753 : 최단경로 https://www.acmicpc.net/problem/1753 최단경로 기본문제. 한 정점을 기준으로 다른 정점까지 최단 경로를 구할때 만약 간선의 가중치가 없으면 BFS로 탐색하면 된다.만약 간선의 가중치가 존재하면 기본적으로 다익스트라(Dijkstra) 알고리즘을 사용할 수 있다. 다익스트라 알고리즘은 BFS와 형태가 유사한데while문에 queue 대신 priority_queue를 넣고 너비우선탐색처럼 정점을 순회하며각 정점의 최단경로를 갱신하는 방법이다. (priority_queue를 쓰는 것은 다익스트라 알고리즘을 ElogV 로 최적화 한 것이다.) 각 정점에 연결된 간선의 정보를 넣고 다음 정점을 탐색할때 만약 (다음 정점의 Distance > 현재정점의 Distance + 간선의 가중치).. 더보기 이전 1 2 3 4 다음
