1249. 보급로

다익스트라 알고리즘을 적용할 수 있을까를 생각해보자

거리 테이블이 2차원이다.  => Matrix의 각 칸을 노드라고 생각하면 역시 그래프이다. 따라서 다익스트라의 거리테이블 1차원이지만 Matrix에서 거리테이블을 2차원으로 구축해도 괜찮다.

 

 

#include <iostream>
#define INFINITI 987654321

using namespace std;

int const MAX_LEN = 101;



bool U[MAX_LEN][MAX_LEN]{ false, }; // 업데이트 필요여부를 확인하기 위한 배열
int D[MAX_LEN][MAX_LEN]{ 0, };

struct pos {
	int x;
	int y;
};

pos extractMin(int N) {
	pos minPos{ 0 };
	int minVal = INFINITI;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (U[i][j] && minVal > D[i][j]) {
				minPos = { i,j };
				minVal = D[i][j];
			}
		}
	}
	return minPos;
}

//right down, left up
int d[4][2]{ {0,1},{-1,0}, {0,-1},{1,0} };

// arr[N] [N]에 도착하면 성공
int findMinPath(int m_arr[MAX_LEN][MAX_LEN], pos start, int N) {
	//다익스트라 사용
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			D[i][j] = INFINITI;
		}
	}

	pos cur = start;
	D[start.x][start.y] = 0;
	U[start.x][start.y] = true;

	while (cur.x !=0 || cur.y !=0) {
		cur = extractMin(N);
		if (cur.x == 0 && cur.y == 0) {
			//더이상 없데이트 할게 없습니다.
			return D[N][N];
		}
		U[cur.x][cur.y] = false;

		for (int i = 0; i < 4; i++) {
			int next_x = cur.x + d[i][0];
			if (next_x < 1 || N < next_x) continue;
			int next_y = cur.y + d[i][1];
			if (next_y < 1 || N < next_y) continue;
			if (D[next_x][next_y] > D[cur.x][cur.y] + m_arr[next_x][next_y]) {
				D[next_x][next_y] = D[cur.x][cur.y] + m_arr[next_x][next_y];
				U[next_x][next_y] = true;
			}
		}
	}
	
}

int main() {
	//freopen("Text.txt", "r", stdin);
	int TC;
	scanf("%d",&TC);
	getchar();
	int res_count[10];
	int m_arr[MAX_LEN][MAX_LEN]{ 0, };
	for (int t = 0; t < TC; t++) {
		int N;
		scanf("%d",&N);
		getchar();
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				m_arr[i][j] = getchar() - '0';
			}
			getchar();
		}

		cout<<"#"<<t+1<<" "<<findMinPath(m_arr, { 1,1 }, N)<<endl;



		//다음 TC를 위한 clean작업
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				m_arr[i][j] = 0;
			}
		}
	}
	
	return 0;
}