(프로그래머스 / Dijkstra) 완주하지 못한 선수

문제 요약

솔루션

Dijstra

상태공간

시간복잡도

구현 순서

코드

#include <iostream>
#include <queue>
using namespace std;
/*
* N 넓이
* MAP 필드의 값
* dist[Y][X] [1][1]로부터 [Y][X]까지의 거리
* q 탐색할 대상 좌표 중 가장 작은 수를 최우선으로 갖는 priority queue
*/
#define MAX 130
int N, MAP[MAX][MAX] = { 0, }, D[4][2] = { {-1,0}, {0, 1}, {1,0}, {0, -1} };
int dist[MAX][MAX];
typedef struct _coords {
	int v;//1,1에서 y,x까지 도달하는 최소값
	int y;
	int x;
} coords;
struct cmp {
	bool operator()(coords& a, coords& b) {
		return a.v > b.v;
	}
};
priority_queue <coords, vector<coords>, cmp> q;
//(1,1)에서 (N,N)까지 가는데 최소비용을 저장하는 함수
int dijkstra() {
	//(1,1)에서 Y,X까지 가는데의 최소값을 dist[Y][X]에 저장
	coords init_coords = { MAP[1][1],1,1 };
	q.push(init_coords);
	while (!q.empty()) {
		coords cur = q.top(); q.pop();
		int cv = cur.v, cy = cur.y, cx = cur.x;
		dist[cy][cx] = cv;

		//cout << cur.v << cur.y << cur.x << endl;
		//현재 좌표에서 접근할 수 있는 좌표들 확인
		for (int d = 0; d < 4; d++) {

			int ny = cy + D[d][0], nx = cx + D[d][1];
			if (ny < 1 || ny > N || nx < 1 || nx > N) continue;

			int nv = cv + MAP[ny][nx];
			if (nv >= dist[ny][nx]) continue;

			q.push({ nv, ny, nx });
			dist[ny][nx] = nv;
			
		}

	}
	return 0;
}
int main() {
	int i, j, num=0;
	while (1) {
		//!초기화
		
		cin >> N;
		if (N == 0) break;
		for (i = 1; i <= N; i++) {
			for (j = 1; j <= N; j++) {
				dist[i][j] = 1e9;
				cin >> MAP[i][j];
			}
		}
		dijkstra();
		cout << "Problem " << ++num << ": " << dist[N][N] << endl;
	}
}

이슈

• 1e9로 나누어 주지 않아 정수 범위를 초과해,,,
  • 자바스크립트와 파이썬에 익숙해지는 바람에 그만,,,