[SWEA] 보급로 - BFS

전형적인 BFS문제이다.
보급로

난이도 : H

다른 블로그들 보니까 굳이 사진을 넣길래 넣어봤다.

배운점

1. 긴 정수형 input의 경우 char 타입으로 받고 '0'을 빼준다.
2. for문 사용시 register을 사용하면 시간 효율성이 좋아진다.
3. 동서남북을 체크하기 위한 dx[],dy[]작성 시 static을 붙이면 시간 효율성이 좋아진다.
4. queue에서 pop을 한 뒤 해당 값을 활용할 가치가 있는지 없는지 부등호 및 등호를 통해 고려하고 continue를 통해 효율성을 가진다.

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

#define MAXN (100)
int T, N;
int arr[MAXN + 2][MAXN + 2], check[MAXN + 2][MAXN + 2];

struct st {
	int r, c,time;

	st(int R=0, int C=0, int T=0) :r (R), c(C), time(T){};
};
queue <st> que;

void InputData() {
	scanf("%d", &N);
	for (register int i = 0; i < N; i++) {
		for (register int j = 0; j < N; j++) {
			char c;
			scanf(" %c", &c);
			arr[i][j] = c - '0';
		}
	}
}
void BFS(int r, int c) {
	st data,ndata;
	data.r = r; data.c = c; data.time = 0;
	que.push(data);
	check[r][c] = 0;
	while (!que.empty()) {
		data = que.front(); que.pop();
		if (check[data.r][data.c] < data.time) continue;

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

		for (register int i = 0; i < 4; i++) {
			ndata.r = data.r + dx[i]; ndata.c = data.c + dy[i]; ndata.time = data.time + arr[ndata.r][ndata.c];
			if (ndata.r < 0 || ndata.r >= N || ndata.c < 0 || ndata.c >= N)continue;//범위 밖
			if (check[ndata.r][ndata.c] <= ndata.time)continue;//비효율
			check[ndata.r][ndata.c] = ndata.time;
			que.push(ndata);
		}
	}
}
void initCheck() {
	for (register int i = 0; i < N; i++) {
		for (register int j = 0; j < N; j++) {
			check[i][j] = 0x7fffffff;
		}
	}
}
void Solve() {
	initCheck();
	BFS(0, 0);
}
int main() {
	scanf("%d", &T);
	for (register int t = 1; t <= T; t++) {
		InputData();
		Solve();
		printf("#%d %d\n", t, check[N - 1][N - 1]);
	}
	return 0;
}