백준152 백준 17396 c++ "백도어" -[PlusUltraCode] https://www.acmicpc.net/problem/17396 [필자 사고] 전형적인 다익스트라 문제이다. 이 문제의 중요한 점은 ward배열이다. 즉 발각 되냐 안되냐에 있다. 와드가 1로 되어 있는 곳은 탐색을 하면 안되므로 그 부분을 신경 써주면 된다. 또한 값들이 매우 크다. int형 범위로는 담을 수 없을수도 있기 때문에 사전에 long으로 바꿔서 문제를 풀어준다. [소스 코드] #include #include #include #include #include #include #include using namespace std; typedef pair Node; int N, M; vector ward; vector Arr; vector pathLoad; vector visited; void .. 2024. 2. 27. 백준 1446 c++ "지름길" -[PlusUltraCode] https://www.acmicpc.net/problem/1446 [필자 사고] 다익스트라 알고리즘을 알고 있다면 쉽게 문제를 해결할 수 있다. 이 문제의 특잉한 점은 모든 index+1 을 그래프로 연결해줘야 된다는 점이다. 또한 도착지점이 D보다 넘어가면 문제가 생기므로 이 또한 주의 해야 된다. [소스 코드] #include #include #include #include #include #include #include using namespace std; typedef pair Node; int N, D; vector Arr; vector pathLoad; void Dijkstra() { priority_queue pq; pq.push({ 0,0 }); pathLoad[0] = 0; while (.. 2024. 2. 27. 백준 14938 c++ "서강그라운드" -[PlusUltraCode] [필자 사고] 문제를 접하고 최단거리 구하는 문제라 생각하였다. 처음에는 다익스트라 알고리즘을 사용하여 문제를 풀었다. 문제를 푸는 중간에 이 문제는 플로이드-워셜 알고리즘을 사용하면 쉽게 해결할 수 있다는 걸 느꼇다. 간단하게 플로이드-워셜 알고리즘을 설명하겠다. 시작 ,중간, 끝 이 있을때 D[시작][끝] =D[시작][중간] + D[중간][끝] 이러한 식이 플로이드 워셜이다. 시간복잡도는 O(n^3)이므로 N의 수를 확인해보니 100정도라 문제 없었다. 다익스트라에만 매몰되지 않고 좀 더 유기적으로 생각해야 할 필요가 있는거 같았다. [소스 코드] #include #include #include #include #include #include #include using namespace std; ty.. 2024. 2. 27. 백준 2665 c++ -[PlusUltraCode] [필자 사고] 이 문제는 2차원 배열에서 다익스트라 알고리즘을 사용하는 교과서적인 문제이다 간단하게 문제를 설명하면 자신이 벽을 부신 횟수를 우선순위큐에 넣어 벽을 부신 수가 적은 index부터 접근하여 문제를 해결해 나가면 쉽게 풀 수 있다. [소스 코드] #include #include #include #include #include #include #include using namespace std; typedef struct Node { int Break; int sero; int garo; }Node; typedef struct cmp { bool operator()(Node a, Node b) { return a.Break > b.Break; } }; int dy[4] = { 0,1,0,-1 .. 2024. 2. 27. 이전 1 ··· 29 30 31 32 33 34 35 ··· 38 다음