반응형 정답24 백준 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. 백준 10282번 - 해킹 (C++) 문제 해결 방법 우선순위 큐(priority_queue)에 현재 감염된 컴퓨터와 연결된 컴퓨터들을 감염시간과 함께 pair 형식으로 넣어주었다. 큐에서 이를 반복하였다. 또한, 소요 시간이 초기값이 아니라면, 이미 한번 이 컴퓨터가 해킹당했고, 우선순위 큐에서 이전에 탐색되었다는 의미는 이미 더 짧은 소요 시간으로 도달할 수 있다는 의미이기 때문에 continue해주었다. 아쉬웠던 점 없음 코드 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 54 55 56 57 58 59 60 61 6.. 2021. 11. 3. 백준 13460번 - 구슬 탈출 2 (C++) 문제 해결 방법 DFS를 사용해서 해결했다... (덕분에 해결 시간은 매우 높다) 실행 방식은 그냥 평범한 DFS... 라서 더 설명할 것이 없다. 구슬의 이동은 따로 구슬의 좌표들을 미리 저장해 구슬을 매번 찾는 손해는 없도록 하였으며, 구현은 그냥 반복을 통하여 이동/탐색하며 빈칸이 아닌 공간을 찾고, 막혀있는 공간을 만난다면 그 바로 이전 칸으로 이동하게끔 하였다. 예외적으로 구멍인 O는 만나면 이동이 아니라 구슬이 삭제되게끔 하였다. 아쉬웠던 점 보자마자 감이 와서 바로 푼 문제인데, BFS로 풀어야 하는데 아무 생각없이 브루트포스(전체탐색)이니 간단한 DFS로 해야겠다~ 라는 안일한 생각을 했다. 사실 최단거리 구하는거면 당연히 BFS를 생각했어야 했는데 수련이 부족한듯 ㅜㅠㅠ 코드 1 2 3 .. 2021. 10. 26. 이전 1 2 3 4 ··· 6 다음 반응형
