반응형 풀이3 백준 1753번 - 최단경로 (C++) 해결 방법다익스트라 문제.시작 간선부터 시작해서, 내가 갈 수 있는 모든 지점의 최단거리를 기록해두고우선순위 큐를 사용하여 그중 가장 낮은 지점부터 다시 모든 지점의 최단거리 기록을 반복한다.+번외로 처음 입력받을 때, 출발지 목적지가 같은 가중치만 다른 간선이 여러개가 입력될 수 있어 최적화를 위해 이건 가장 짧은 간선 하나만 받아올 수 있도록 했다.아쉬웠던 점우선순위 큐의 존재를 모르고 일반 큐로 최소값 찾고 하면서 했다가 시간초과 나서 우선순위 큐는 검색을 통해 알게 되었다. 번외로, 기본적으로 우선순위 큐의 정렬은 오름차순인데 이걸 내림차순으로 변경하기 위해 자료형을 지정해주는게 참 괴상하게 생긴듯.코드12345678910111213141516171819202122232425262728293031.. 2025. 1. 9. 백준 1149번 - RGB거리 (C++) 해결 방법DP문제.n*3 크기의 dp에 현재 수와, 그 이전까지 의 합(dp)를 더해서 최대값을 찾아 저장한다.이후 가장 마지막 줄의 3칸중 가장 낮은 값이 정답.코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include iostream>using namespace std; int dp[3][1001];int rgb[3][1001]; int GetMin(int a, int b){ if(a==0) return b; if(b==0) return a; return a > b ? b : a;} int.. 2025. 1. 8. 백준 2252번 - 줄 세우기 (C++) 문제 해결 방법 위상 정렬을 사용하는 대표적인 문제이다. 정점기준 보내주는 간선들의 숫자, 받은 간선의 횟수를 저장하는 배열을 만들어서 이를 기반으로 큐를 사용하여 위상정렬을 했다. 아쉬웠던 점 초기에 큐에 넣는 과정을 입력구간에서 어떻게 잘 해결할 수 있을 것 같기도 한데, 결국 받은 간선을 저장한 배열을 순회하며 그 숫자가 0인 정점을 일일이 찾은게 뭔가 아쉽다. 코드 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 #include #include #include using namespace std; int m.. 2021. 10. 8. 이전 1 다음 반응형
