BOJ 4485 녹색 옷 입은 애가 젤다지?

www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

 

BFS + 다익스트라 조합으로 풀면 된다.

기존 다익스트라는 1차원 배열에서 각 정점의 최단거리를 구했지만

이 문제에서는 2차원 배열로 선언해서 각 구간에 가기 위해서 우선순위 큐를 사용해서

최단거리로 갱신하며 이동한다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
int ar[126][126], n;
bool vis[126][126];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

vector<vector<int>> dijkstra(int x, int y) {
	priority_queue<pair<int, pair<int, int>>> pq;
	vector<vector<int>> d(n, vector<int>(n, inf));
	for (int i = 0; i < n; ++i) fill(vis[i], vis[i] + n, false);

	d[x][y] = ar[x][y];
	pq.push({ -ar[x][y],{x,y} });
	vis[x][y] = true;
	
	while (!pq.empty()) {
		auto cur = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (d[cur.first][cur.second] < cost) continue; //현재 거리가 경유해온 거리보다 작다면 패스
		for (int i = 0; i < 4; ++i) { 
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; 
			if (vis[nx][ny]) continue; //방문했다면 패스
			vis[nx][ny] = true;
			int nc = cost + ar[nx][ny];
			if (nc < d[nx][ny]) { //갱신할 수 있다면 갱신해주기
				d[nx][ny] = nc;
				pq.push({ -nc,{nx,ny} });
			}
		}
	}

	return d;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int tc = 1;
	while (1) {

		cin >> n;
		if (n == 0) break;

		for (int i = 0; i < n; ++i) 
			for (int j = 0; j < n; ++j) 
				cin >> ar[i][j];

		vector<vector<int>> d = dijkstra(0, 0);

		cout << "Problem " << tc++ << ": " << d[n - 1][n - 1] << '\n';
	}

	return 0;
}

 

테스트 케이스가 주어지는 문제는 항상 초기화를 잘해줘야 한다.