#83 문제는 난이도 25%로 설정되어 있습니다. 동적 계획법 등으로는 구현하기 어렵고, 다익스트라 알고리즘을 사용해야 합니다.
다익스트라 알고리즘 자체는 너비 우선 탐색, 프림 알고리즘과 비슷한 구현 방법으로 큐 자료구조와 우선순위 큐 자료구조의 이해가 필요합니다.
https://projecteuler.net/problem=83
다익스트라 알고리즘 구현은 그래프에서 경로 찾기에서 자주 나옵니다.
다익스트라 알고리즘
다익스트라 알고리즘은 시작점에서 다른 모든 경로로 가는 최단 거리에 대한 그래프(트리)를 만들어줍니다. 다익스트라 알고리즘을 사용하려면, 힙을 이용해서 최소의 엔티티를 찾는 것이 필요
sdev.tistory.com
#1445 일요일 아침의 데이트
일요일 아침의 데이트는 다익스트라 알고리즘을 이용하는 문제로 Gold II 문제로 잡혀 있습니다. 아침에 산책을 하면서 야외에서 커피를 같이 마시면 즐겁겠죠? 다익스트라 알고리즘을 알고 있는
sdev.tistory.com
제가 작성한 소스입니다.
#include <cstdio>
#include <queue>
using namespace std;
#define FILENAME "p083_matrix.txt"
#define INFTY 1000000000
struct qnode
{
int sum, row, col;
qnode(int s, int r, int c) : sum(s), row(r), col(c) { }
bool operator<(const qnode node) const { return sum > node.sum; }
};
int solve1(int d[][80])
{
priority_queue<qnode> queue;
static int v[80][80];
static char visited[80][80];
for(int i=0; i<80; i++) for(int j=0; j<80; j++) v[i][j] = INFTY;
v[0][0] = d[0][0];
queue.push(qnode(d[0][0], 0, 0));
for(;;)
{
qnode node = queue.top(); queue.pop();
if(visited[node.row][node.col]) continue;
if(node.row == 79 && node.col == 79 ) return node.sum;
visited[node.row][node.col] = 1;
const int off[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };
for( int i = 0 ; i < 4 ; i++ )
{
int nrow = node.row + off[i][0];
int ncol = node.col + off[i][1];
if( nrow < 0 || ncol < 0 || nrow >= 80 || ncol >= 80 ) continue;
if( visited[nrow][ncol] ) continue;
int nsum = node.sum + d[nrow][ncol];
if(nsum < v[nrow][ncol])
{
v[nrow][ncol] = nsum;
queue.push(qnode(nsum, nrow, ncol));
}
}
}
}
int main()
{
static int d[80][80];
FILE *fi = fopen(FILENAME, "r");
for(int r=0; r<80; r++) for(int c=0; c<80; c++)
fscanf(fi, "%d%*c", &d[r][c]);
fclose(fi);
printf("ans = %d\n", solve1(d));
}
반응형
'Programming > Project Euler' 카테고리의 다른 글
[C/C++] 프로젝트 오일러 #85 Counting Rectangles(Brute Force) (0) | 2024.10.08 |
---|---|
[C/C++] 프로젝트 오일러 #84 모노폴리 확률(몬테카를로) (0) | 2023.05.20 |
[C/C++] 프로젝트 오일러 #82 path sum : three ways(다익스트라) (0) | 2022.10.10 |
[C/C++] 프로젝트 오일러 #81 Path sum : two ways(동적 계획법) (0) | 2022.09.26 |
[Python] 프로젝트오일러 #80 제곱근 확장(수학) (0) | 2022.09.13 |
댓글