SWEA 1249 <-클릭

최저 비용으로 경로를 탐색하는 문제다.

문제의 조건을 2차원 배열 map으로 받았다.

또한, 특정 위치로 갈 때의 최소의 비용을 저장하는 2차원 배열을 cost로 하였다.
예) cost[i][j]는 (i,j)로 가는 (지금 껏 계산한) 최소한의 비용이다.

cost는 지금 껏 계산한 비용보다 저렴한 비용으로 방문이 가능하면 해당 값으로 갱신한다.

if (cost[nx][ny] > cost[idx_x][idx_y] + map[nx][ny]) {
	cost[nx][ny] = cost[idx_x][idx_y] + map[nx][ny];
	Q.push(make_pair(nx, ny));
}

갱신만 하면 끝이 아니다. 이 갱신으로 영향을 받을 수 있는 주변 좌표들 또한 재 갱신을 해야 하기에 해당 좌표를 다신 방문해야 하므로 다시 queue에 넣어야 한다.

코드

깃허브

#define _CRT_SECURE_NO_WARNINGS
#define INF 987654321
#include<iostream>
#include<queue>

using namespace std;

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int N;

int map[100][100];
int visited[100][100] = { 0, };
int cost[100][100] = { 0, };
int solve();
void init();
queue<pair<int, int>> Q; //방문 리스트

int main() {
	//freopen("input/1249_input.txt", "r", stdin);
	int testcase;
	cin >> testcase;
	for (int C = 1; C <= testcase; C++) {
		cin >> N;
		init();
		string input;
		for (int i = 0; i < N; i++) {
			cin >> input;
			for (int j = 0; j < N; j++) {
				map[i][j] = input[j] - '0';
			}
		}
		cout << "#" << C <<" " <<solve() << endl;
	}
	return 0;
}

int solve() {
	int idx_x = 0, idx_y = 0;
	Q.push(make_pair(0, 0));
	while (!Q.empty()) {
		idx_x = Q.front().first;
		idx_y = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = idx_x + dx[i];
			int ny = idx_y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if (cost[nx][ny] > cost[idx_x][idx_y] + map[nx][ny]) {
				cost[nx][ny] = cost[idx_x][idx_y] + map[nx][ny];
				Q.push(make_pair(nx, ny));
			}
		}
	}
	return cost[N - 1][N - 1];
}

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] = 0;
			cost[i][j] = INF;
		}
	}
	cost[0][0] = 0;
}

정답 ~.~