Doby's Lab

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 답을 구하는 순서는 쉽게 알아낼 수 있었다. 1) 다익스트라를 통해 최단 경로 탐색 2) 해당 최단 경로를 없앰 3) 다시 한번 다익스트라를 통해 최단 경로를 구함 '해당 최단 경로를 없앰'을 해결하는 게 이번 문제의 핵심이다. 솔루션을 참고(https://jaimemin.tistory.com/617)하기도 했고, 바로 전에 풀었던 문제에서 '경로 역추적'이라는 키워..

https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 이번 문제에서 해결해야 하는 건 "최단 경로를 구했을 때 시작 노드에서 제일 처음 방문한 노드가 어디인가"를 어떻게 찾을지가 포인트였다. (참고 https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-1719-%ED%83%9D%EB%B0%B0) 참고한 포스팅에서 다음과 같이 정리할 수 있었다. 1) 다익스트라를 통해 각 노드로부터 최단 경로 구하기 2) 최단 거..

https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 문제에서 하란대로 간선의 순서까지 조정하며 간선을 추가할 때마다 다익스트라를 돌려야 할 거 같지만 이는 헷갈리게 하려는 의도다. 그냥 다익스트라 한 번 돌리면 끝이다. #include #include #include #include #define MAX 5000 + 1 #define INF 987654321 #define pii pair using namespace std; vector gr..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2차원 배열 형식의 다익스트라는 처음이었다. 헷갈릴 수 있었던 포인트는 1) 구조체를 먼저 선언 2) 비용 초기값 0으로 초기화하지 않기 3) 복잡한 타입으로 인한 지저분한 코드 #include #include #include #include #define MAX 125 #define INF 987654321 using namespace std; int graph[MAX][MAX..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net [방법] s->g->h->x or s->h->g->x가 s->x로 가는 경로 중에 최단 경로여야 한다. 가중치 모두 양수이므로 다익스트라 알고리즘이 사용 가능하다. (경로를 구하는 방식은 이 문제를 통해 공부를 했었다. https://draw-code-boy.tistory.com/138) int path1_1 = fromS[g] + fromG[h] + fromH[x]; int path1_2 ..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 1) "a가 b에 s만큼의 의존성을 가지고 있다." == "b에서 a로 가는 비용이 s다." >> 다익스트라 사용 2) 그래프를 전역 변수로 선언했기 때문에 한 케이스가 끝나면 그래프를 리셋을 해주었다.>> >> 사실 vector graph[MAX]를 인자로 넘기는 방법을 몰랐음. >> 인자로 넘기는 방법을 알면 리셋하는 시간이 없어져서 조금 줄일 수 있지 않을까 싶다. 3) 거리가 INF인 것은 넘..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 일반적인 다익스트라(우선순위 큐 사용)를 제출하면 시간 초과가 난다. 우선순위 큐에서 현재의 top이 도착하려는 노드(v2)가 되면 이미 최소 비용은 구했기 때문에 다른 노드를 향한 최소 비용을 구할 필요 없이 바로 종료시켜줬다. [AC 코드] #include #include #include #include #define MAX 1000 + 1 #define IN..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 이 문제는 다익스트라를 활용한 응용력을 필요로 했다. 주어진 v1, v2를 거치는 경로를 어떻게 필수적으로 보낼지 생각해야 한다. (참고 https://jaimemin.tistory.com/1004) 우선순위 큐에 3개의 원소(노드, 비용, v1 or v2를 지났는가의 여부)를 고민했지만 이는 더 심오한 코드가 만들어졌었다. 그래서 참고를 했다. 이 솔..