백준189 백준 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. 백준 1261 c++ -[PlusUltraCode] [필자 사고] 다익스트라를 이용하여 푸는 문제이다. 이 문제에서 느낀점은 기존 다익스트라 문제에서 방문한 곳은 다시 방문 하지 않았다. 그 이유는 방문한 시점에서 이미 최단거리이기 때문에 시간복잡도를 더욱 효율적으로 하기 위해 방문하지 않았다. 다만 이 문제는 벽을 뿌신 개수의 최소값을 중점으로 두기 때문에 이미 방문한 곳이라도 벽을 부신 횟수를 비교해서 더욱 작은값이 있다면 새로 갱신해줘야 된다는 것이다. 또한 우선순위큐를 항상 pair 로 사용했지만 직접 구조체를 만들어서 Node를 사용할 때는 정렬 함수를 따로 정의해줘야 된다. 안그러면 < 연산자에서 오류가 발생한다. [소스 코드] #include #include #include #include #include using namespace std;.. 2024. 2. 26. 이전 1 ··· 39 40 41 42 43 44 45 ··· 48 다음