SWEA 1249. [S/W 문제해결 응용] 4일차 - 보급로 (C++)

#include <stdio.h>
#include <queue>

using namespace std;

int N;
int map[101][101];
int dist[101][101];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int visited[101][101];
queue<pair<int, int>> q;

void initialize()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			dist[i][j] = 0;
			visited[i][j] = 0;
		}
	}
}

void solve(int x, int y)
{
	q.push(make_pair(x, y));
	visited[x][y] = 1;

	while (!q.empty())
	{
		int cntx = q.front().first;
		int cnty = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = dx[i] + cntx;
			int ny = dy[i] + cnty;

			if (nx < 0 || ny < 0 || nx >= N || ny >= N)
				continue;
			if (!visited[nx][ny] || dist[nx][ny] > dist[cntx][cnty] + map[nx][ny])
			{
				q.push({ nx, ny });
				dist[nx][ny] = dist[cntx][cnty] + map[nx][ny];
				visited[nx][ny] = 1;
			}
		}
	}
}
int main()
{
	int tc;
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++)
	{
		scanf("%d", &N);
		initialize();
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				scanf("%1d", &map[i][j]);
			}
		}
		solve(0, 0);
		printf("#%d %d\n", t, dist[N - 1][N - 1]);
	}
	return 0;
}

1. bfs 사용

좀 어렵게 푼거 같아서 다시 풀어봐야겠땅