[SWEA 1249] 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

#include <cstdio>
#include <cstring>
#include <queue>
int T;
int N;
char in[100 + 2][100 + 2];
int road[100 + 2][100 + 2];	// 최대 100 * 100

struct _st
{
	int x, y;
	int cost;
};

struct COMP
{
	bool operator()(const _st &a, const _st &b)
	{
		return a.cost > b.cost;
	}
};

std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int visited[100 + 2][100 + 2];


void init()
{
	memset(in, '0', sizeof(in));
	memset(road, 0, sizeof(road));
}


void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", &in[i]);
		for (int j = 0; j < N; j++) {
			road[i][j] = in[i][j] - '0';
		}
	}
}


int get_cost()
{
	// init
	memset(visited, 0, sizeof(visited));
	PQ = {};

	// dir
	int dir_x[4] = { 0, 0 ,1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	PQ.push({ 0, 0, 0 });
	visited[0][0] = 1;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.x == N - 1 && data.y == N - 1) return data.cost;

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny]) continue;
			PQ.push({ nx, ny, data.cost + road[nx][ny] });
			visited[nx][ny] = 1;
		}
	}
}



int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		init();
		input();
		printf("#%d %d\n", t, get_cost());
	}
	return 0;
}

각 칸 마다 cost가 다르므로 PQ