전체 글354 백준 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. 백준 4485 c++ -[PlusUltraCode] [필자 사고] 이 문제는 전형적인 다익스트라 알고리즘의 응용버전이다 필자는 대부분 1차원에서 다익스트라 알고리즘을 사용했다면 이 문제를 통해 2차원까지 확장하는 개념을 얻을 수 있게 되었다. 간단하게 다익스트라 알고리즘을 설명하자면 우선순위 큐에 가장 적은 비용의 index부터 탐색하는 방식이다. 2차원개념과 다익스트라 알고리즘을 알고 있다면 쉽게 해결할 수 있는 문제이다. [소스 코드] #include #include #include #include #include using namespace std; int dy[4] = { 0,1,0,-1 }; int dx[4] = { 1,0,-1,0 }; typedef struct Node { int cost; int sero; int garo; }Node; ty.. 2024. 2. 27. 백준 11779 c++ -[PlusUltraCode] [필자 사고] 전형적인 다익스트라 알고리즘을 사용하여 푸는 문제이다. 이 문제의 특이한 점은 최단거리의 지나간 경로를 저장해야 된다는 점이다. 지나간 경로를 저장하는 방법은 크게 2가지가 있다. 트리형태로 배열을 만들어 부모노드와 자식노드를 연결하는 방법과 백트래킹을 이용하여 역추적 하는 방법이 있다. 필자는 백트래킹을 이용하여 문제를 해결했다. 백트래킹을 잠깐 설명하겠다. 1. 시작지점에서 다익스트라 알고리즘을 적용하면 최단 거리가 만들어진다. 2. 원래 저장해놨던 그래프 방향을 반대로 해놓은 상태를 새로운 배열에 저장한다. 3. 끝 지점부터 현재값-비용=다음값 과 같은 형태를 찾으면 된다. [소스코드] #include #include #include #include #include using name.. 2024. 2. 27. 이전 1 ··· 78 79 80 81 82 83 84 ··· 89 다음