Solution & Idea
- 문제는
(0,0)에서 시작해(N-1, N-1)까지 갈 때 최소 비용을 구하는 것 - 처음에는 dp를 풀 때 외발뛰기, 삼각형 위의 최대 경로 같은 문제들을 생각하며 dp로 풀어야 하나 생각했지만 링크는 동서남북으로 움직일 수 있으며 그때마다 이미 구했던 최적의 해는 바뀔 수 있다
BFS를 이용한 완전 탐색을 이용- 비용의 모든 수는 0~9사이의 음이 아닌 정수 이므로
Dijkstra사용 가능
1. BFS- Brute Force
- 각 위치에서 최소 비용을 나타내는 배열 d[][]를 만들고 INF로 초기화
- 처음 d[0][0]=map[0][0]으로 초기화
- 현재 위치
(y,x)에서 상하좌우로 인접한 위치(ny,nx)의 최소 비용을 탐색하는데d[ny][nx] (=(0,0)에서 (ny,nx)까지 구해놓은 최소 비용)의 값이d[y][x]+map[ny][nx] (=현재 위치에서 이동해서 가는 비용)보다 크다면 새로 업데이트 해준다 - 업데이트 된 위치를 다시
queue에 넣어준다
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
#define INF 9999
const int MAX = 126;
const int dy[] = { 0,0,1,-1 };
const int dx[] = { 1,-1,0,0 };
using namespace std;
int N;
int map[MAX][MAX];
int d[MAX][MAX];
void init() {
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
d[i][j] = INF;
}
}
}
void find() {
d[0][0] = map[0][0];
queue<pair<int, int> >q;
q.push(make_pair(0, 0));
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (d[ny][nx] > d[y][x] + map[ny][nx]) {
d[ny][nx] = d[y][x] + map[ny][nx];
q.push(make_pair(ny, nx));
}
}
}
}
void solution() {
int idx = 0;
while (true) {
idx++;
init();
cin >> N;
if (N == 0) break;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> map[i][j];
find();
printf("Problem %d: %d\n", idx, d[N - 1][N - 1]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solution();
}
2. Dijkstra
-
다익스트라 알고리즘은
너비 우선 탐색과 유사한 형태를 가진 알고리즘 (가중치가 있는 그래프에서는 너비 우선 탐색을 그대로 적용할 수 없음, 더 늦게 발견한 정점이라도 더 먼저 방문할 수 있어야 한다는 의미) -
시작점에서 가까운 순서대로 정점을 방문해감
-
우선순위 큐에 정점의 번호와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣음 -
아직 방문하지 않은 정점 중 시작점으로부터 거리가 가장 가까운 점을 찾는 과정을 간단하게 해줌
-
각 정점까지의
최단 경로는 갱신될 수 있음 -
코드에서 방문한 정점과 방문하지 않은 정점을 구분하지 않는 경우 실제로는 음수 사이클만 없다면 음수 간선이 있는 그래프에서도 동작을 하긴 함 -> 정점의 갯수에 대해 지수적으로 증가할 수 있기 때문에 알고리즘의 시간 복잡도가 기하 급수적으로 증가함 -> 권장하지 않음
-
우선 순위 큐를 사용하지 않은 다익스트라 알고리즘 구현
( 정점의 수가 적거나 간선의 수가 매우 많은 경우-> 방문해야 할 정점의 목록을 저장하는 큐가 따로 없기 때문에 각 정점을 방문했는지 여부를 나타내는 별도의 배열 visited[]를 유지)
vector<int> dijkstra2(int src) {
vector<int> dist(N, INF);
vector<bool> visited(N, false);
dist[src] = 0; visited[src] = false;
while (true) {
int closest = INF, here;
for (int i = 0; i < N; i++) {
//아직 한 번도 방문되지 않고 가장 가까운 정점을 찾음
if (dist[i] < closest && !visited[i]) {
here = i;
closest = dist[i];
}
}
if (closest == INF) break;
visited[here] = true;
for (int i = 0; i < adj[here].size(); i++) {
int there = adj[here][i].first;
if (visited[there]) continue;
int nextDist = dist[here] + adj[here][i].second;
dist[there] = min(dist[there], nextDist);
}
}
return dist;
}Dijkstra- priority_queue를 이용한 문제 풀이
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
#define INF 9999
const int MAX = 126;
const int dy[] = { 0,0,1,-1 };
const int dx[] = { 1,-1,0,0 };
using namespace std;
int N;
int map[MAX][MAX];
int d[MAX][MAX];
void init() {
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
d[i][j] = INF;
}
}
}
void find() {
d[0][0] = map[0][0];
queue<pair<int, int> >q;
q.push(make_pair(0, 0));
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (d[ny][nx] > d[y][x] + map[ny][nx]) {
d[ny][nx] = d[y][x] + map[ny][nx];
q.push(make_pair(ny, nx));
}
}
}
}
void solution() {
int idx = 0;
while (true) {
idx++;
init();
cin >> N;
if (N == 0) break;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> map[i][j];
find();
printf("Problem %d: %d\n", idx, d[N - 1][N - 1]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solution();
}
Backend 개발자 지망생