기록을

https://www.acmicpc.net/problem/17142

문제 설명

1. 비활성 바이러스의 위치가 여러곳 주어진다.

2. 그 중에서 M개를 선택해서 확산 바이러스로 만들고, 바이러스의 확산을 시작한다.

(확산 바이러스는 비활성 바이러스를 만나면 그 비활성 바이러스를 확산 바이러스로 바꾼다)

3. 바이러스가 전부 퍼질 때까지 걸린 시간의 최솟값을 구하여라.

문제를 시작하기 전에 몇가지 표현을 잘 이해하고 들어가야한다.

먼저 문제가 구하라고 한 것은, 바이러스가 다 퍼질 때까지 걸린 최소 시간이다. 퍼지는 바이러스가 활성 바이러스여야 한다는 말은 없다.

테스트케이스를 좋게 주지 않았더라면 괴랄한 정답률을 보여주지 않았을까 생각한다.

아래쪽에 있는 테스트 케이스를 활용하면 대부분의 엣지 케이스에 대한 감을 잡을 수 있을 것이다.

[알고리즘]

1. 백트레킹을 활용해서 전체 바이러스 중에서 m개를 선택한다.

2. 선택한 m개의 바이러스를 큐에 넣고 BFS를 돌린다.

3. 빈칸과 비활성 바이러스가 있으면서 방문하지 않은 지점이면 바이러스를 확산시키고, 시간을 기록한다.

4. 시간이 얼마 걸렸는지 파악하기 위해 방문처리 배열 내에서 최댓값을 찾는다. 이 때 최댓값을 선택할 때 그 지점이 바이러스가 위치하고 있는 지점이라면 최댓값으로 보지 않는다.

마지막 테스트 케이스에서와 같이, 이미 바이러스로 채워져있는 곳은 사실 방문할 필요가 없었던 지점이다. 하지만 거쳐가면서 확산이 이루어져야 하기 때문에 일단 채택은 하고, 바이러스가 전체로 퍼지는 시간에는 영향을 끼치면 안되기 때문에 제외해준다.

5. 위에서 구한 최댓값(시간)의 최솟값을 답으로 정한다.

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;

int n, m, map[51][51], dis[51][51], arr[11], st = 0; //연구소 크기, 바이러스 개수
bool isused[11];
struct VIRUS {
	int r;
	int c;
};
vector<VIRUS> v;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int res = INT_MAX;

void bfs() {
	
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
			if (dis[nr][nc] >= 0 || map[nr][nc] == 1) continue;
			
			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
		}
	}
}
void init() {
	for(int i = 0 ; i < n ; i++)
		for (int j = 0; j < n; j++) 
			dis[i][j] = -1;
}
bool isDone(){
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] == -1 && map[i][j] != 1)
				return false;
		}
	}
	return true;
}
void findMax() {
	int Max = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (Max < dis[i][j] && map[i][j] != 2) 
				Max = dis[i][j];

	if (res > Max) res = Max;
}
void func(int k) {
	if (k == m) {

		for (int i = 0; i < m; i++) {
			int r = v[arr[i]].r;
			int c = v[arr[i]].c;
			q.push({ r, c });
			dis[r][c]++;
		}
		bfs();

		if (isDone()) 
			findMax();
		
		init();

		return;
	}

	if (k == 0) st = 0;
	for (int i = st; i < v.size(); i++) {
		if (!isused[i]) {
			arr[k] = i;
			st = i;
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dis[i][j] = -1;
			if (map[i][j] == 2) { //바이러스 위치 저장
				VIRUS tmp;
				tmp.r = i;
				tmp.c = j;
				v.push_back(tmp);
			}
		}

	func(0);

	if (res == INT_MAX) cout << -1 << '\n';
	else
		cout << res;
	return 0;
}

https://www.acmicpc.net/problem/17143

필요한 상어에 대한 정보를 담아서 구조체를 만든다.

이후에는 착실하게 시뮬레이션을 진행해주면 된다.

나 같은 경우에는 이전에 나무재테크 문제를 풀 때를 떠올려서, 한 칸에 상어가 여러 마리 들어가는 경우가 생기기 때문에 배열로 벡터를 잡았다.

먼저 상어의 이동과 관련된 구현이다.

문제에서 상어의 속력은 1000까지 가능하다고 했는데, 이 부분에서 나름 연산의 횟수를 줄여보겠다고 행과 열의 길이를 활용해서 모듈러 연산을 사용했다.

그런데 생각하지 못한 부분이 있었어서 프린트를 찍어가며 디버깅을 하는 데에 애를 먹었다.

그냥 속편하게 속도만큼 반복문을 돌리면서 (완벽한 통제를 위해서 for문을 사용하는 것이 낫겠다) 속도만큼 칸을 이동해주고, 이동한 칸이 범위를 벗어난다면 다시 바로잡아주는 식으로 하는 것이 조금 더 쉽고 직관적으로 구현할 수 있는 방법인 것 같다.

다른 부분은 상어가 먹히는 부분이다.

나는 일단 상어는 다 칸에 들어갈 수 있고, 그 이후에 가장 큰 상어를 찾아서 그 상어만 두고 나머지 상어는 다 제거하는 방식으로 구현을 했다.

간단하게 auto를 사용하지 않고, iterator를 선언하는 방법과, 이를 이용해서 출력하는 것을 코드로 나타내었다.

내용은 향후에 추가될 예정이다.

#include<iostream>
#include<list>
using namespace std;

int main(void) {

	list<int> L = { 1, 2 };
	list<int>::iterator it = L.begin(); //iterator를 포인터라고 생각하면 편하다
	
	cout << *it << '\n';
	L.push_back(3);
	it++;
	it++; //한칸씩 움직인다
	cout << *it << '\n'; //3을 가리킴

	//여기까지 1,2,3

	L.insert(it, 10); //it는 3 가리키고있었는데 왼쪽에 10이 추가됨. it는 여전히 3 가리킴

	L.insert(it, 15); //3가리키는 it왼쪽에 15추가

					  //전체 리스트 출력
	for (list<int>::iterator itor = L.begin(); itor != L.end(); itor++) {
		cout << *itor << ' ';
	}
	
	cout <<'\n' << *it << '\n';

	it = L.erase(it);
	it--;

	
	for (list<int>::iterator itor = L.begin(); itor != L.end(); itor++) {
		cout << *itor << ' ';
	}

	cout << '\n' << *it << '\n';

	it = L.end(); // 리스트의 끝보다 한칸 더 오른쪽의 값을 가리킨다
	it--; //그러니까 하나 당겨주고 
	cout << '\n' << *it << '\n'; //출력해야 마지막 값이 나온다

	it = L.begin();
	cout << '\n' << *it << '\n'; //처음 값
	return 0;
}

https://www.acmicpc.net/problem/16235

특별한 알고리즘이랄 것이 없지만, 벡터를 활용하는 약간의 센스가 필요하다.

정수를 담는 벡터 자료형을 이차원 배열로 선언한다.

그래야 이차원 좌표상의 한 공간에 나무가 여러개 쌓이는 효과를 볼 수 있다.

그리고, 여름에 나무의 삭제가 발생할 때, 삭제되는 나무에 대한 처리를 할 때, vector.erase를 사용하고, 삭제되는 나무들에 대한 정보를 큐로 옮긴 이후에, 큐에서 pop하면서 처리를 해서 시간초과를 받았다.

이를 해결하기위해서, 봄에 땅으로부터 영양분을 흡수하는 것은 어짜피 나무가 나이로 정렬된 상태로 이루어지고, 특정 나이가 땅의 양분보다 많은 순간이 온다면, 그 나무보다 나이가 많은 나무들은 자연스럽게 확인할 가치가 없어지기 때문에, 봄에 영양분을 흡수했던 나무들을 임시 벡터에 넣어두고, 실패지점 이후에 원본 벡터를 clear한 이후에, 임시 벡터에 들어있는 데이터를 원래 벡터에 옮겨주면 여름에 대한 구현을 할 수 있다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll grd[11][11];
int igr[11][11], n, m, k;
vector<ll> v[11][11];
int dr[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int main(void) {
	//1-indexed
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> igr[i][j];
			grd[i][j] = 5;
		}
	}
	for (int i = 1; i <= m; i++) {
		int r, c, age;
		cin >> r >> c >> age;
		v[r][c].push_back(age);
	}
	for (int i = 1; i <= k; i++) {
		//봄
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (v[i][j].size() > 0) { //i행 j열에 나무가 존재하면
					vector<ll> tmp;
					sort(v[i][j].begin(), v[i][j].end()); //어린 나무부터
					//땅양분이 나이보다 많으면 나이 증가, 땅 양분 감소
					ll dead = 0;
					for (int t = 0; t < v[i][j].size(); t++) {
						if (v[i][j][t] <= grd[i][j]) {
							tmp.push_back(v[i][j][t] + 1);
							grd[i][j] -= v[i][j][t];
						}
						else {
							dead += v[i][j][t] / 2;
						}
					}
					//여름
					v[i][j].clear();
					v[i][j] = tmp;
					grd[i][j] += dead;
				}
			}
		}

		//가을
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (v[i][j].size() > 0) {
					for (int t = 0; t < v[i][j].size(); t++) {
						if (v[i][j][t] % 5 == 0) {
							for (int ii = 0; ii < 8; ii++) {
								int nr = i + dr[ii];
								int nc = j + dc[ii];
								if (nr < 1 || nc < 1 || nr > n || nc > n) continue;
								v[nr][nc].push_back(1);
							}
						}
					}
				}
			}
		}

		//겨울
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				grd[i][j] += igr[i][j];
			}
		}
	}
	ll cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (v[i][j].size() > 0) cnt += v[i][j].size();
		}
	}
	cout << cnt;
	return 0;
}

가령 X & Y 라는 수식이 있다고 하자. 이 때 &자리에는 | 그리고 ^도 올 수 있다.

순서대로 and, or, xor을 의미한다.

X와 Y를 이진수로 바꾸고, 각 자릿수의 비트를 해당 연산자에 맞게 연산해서 그 결과를 반환해준다.

일반 연산보다 연산 속도가 빠르다.

가령 2 & 3을 계산한다고 하면, 2는 이진수로 0000010, 3은 00000011이다.

왼쪽의 6자리 0끼리는 and 연산해봐야 0이므로 놔두고, 1 & 1 = 1, 0 & 1 = 0이기 때문에, 연산의 결과는

00000010 = 십진수로 2라고 할 수 있다.

삼항 연산자에 대해 알아보자.

조건식? 식1 : 식2

위와 같이 사용되는데, 조건식이 참이라면 식1이 실행되고, 거짓이라면 식2가 실행된다는 의미이다.

package pjtTest;

public class MainClass {
	public static void main(String[] args) {
		int Big = 10, Small = 5;
		boolean result;
		result = (Big > Small) ? true : false;
		System.out.printf("result = %b", result);
	}
}

자바에서는 System.out..println("");으로 출력을 하곤 한다.

하지만 C++에서 익숙하게 사용해오던 %d, %c 등의 서식 문자를 사용하기 위해서는  println을 printf로 바꿔서 사용해줘야 한다.

f가 format의 약자라서 그렇다고 한다. 또한 println은 개행(줄 바꿈)을 포함하고 있다. 하지만 printf는 개행이 포함되지 않기 때문에 줄 바꿈을 직접 해줘야 한다.

10진수로 %d를 사용했다면, 8진수는 %o 16진수는 %x를 사용한다.

또한 정수와 실수의 자릿수를 제한할 때도 서식 문자를 사용할 수 있다.

정수의 경우, 오른쪽 정렬을 할 때에 서식문자를 활용하여 아래와 같이 할 수 있고,

실수의 경우에는, %.숫자f를 활용하여 소수점 자릿수를 제한할 수 있다.

package pjtTest;

public class MainClass {
	public static void main(String[] args) {
		//여러개의 클레스를 만들어 놓거나 하면, 컴퓨터는 뭘 실행해야 할지 모른다.
		//main 메소드부터 실행한다.
		
		//10의 10, 8, 16진수 출력
		int num = 10;
		System.out.printf("10진수 %d\n",num);
		System.out.printf("8진수 %o\n", num);
		System.out.printf("16진수 %x\n", num);
		System.out.println("\n");
		
		//숫자들을 오른쪽 정렬해서 출력하고 싶을 때
		System.out.printf("%5d\n",123);
		System.out.printf("%5d\n",1234);
		System.out.printf("%5d\n",12345);
		
		//소수점 자리수를 제한하고 싶을 때
		double num2 = 3.141592;
		System.out.printf("%.1f\n",num2);
		System.out.printf("%.3f\n",num2);
		System.out.printf("%.5f\n",num2);
	}
}

 https://www.acmicpc.net/problem/16234

bfs 혹은 dfs를 활용하여 해결할 수 있다.

인구이동 조건과, 방문 여부가 탐색 진행의 기준이 된다.

for(for(bfs)) 구조로 해결할 수 있다.

for(for 을 완전히 탈출할 때 까지가 한 번의 인구이동 날이라고 할 수 있다.

따라서 이를 무한루프로 감싸서, 인구의 이동이 없는 경우 무한루프를 탈출하는 구조로 해결하면 된다.

그런데, 인구 이동 조건을 만족하더라도, 그 자리에서 인구수를 바로 갱신할 수가 없다.

일단 국경을 개방할 수 있는 지점을 모두 찾아내야 하기 때문에, 일단 한 번의 bfs가 다 종료되어야 인구수를 갱신할 수 있다. 방문처리된 지점들(큐에 삽입된 적이 있는 지점들)이 갱신의 대상이기 때문에, 이 좌표들을 차례로 백터에 저장해준다.

이후에 벡터의 크기가 연합국의 숫자이고, 인구수의 합은 큐에 삽입하면서 기억해 둘 것이다.

한번의 인구 이동이 모두 끝났는데, 변화가 없다면 무한 루프를 종료하고, 그렇지 않다면 방문처리 배열을 초기화해준 이후에 인구이동을 다시 시작해주면 된다.

#include<iostream>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
int N, L, R, m[51][51];
bool bor[51][51]; //방문 처리 배열
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };

queue<pair<int, int> > q;
bool updated = false;
int idxSum = 0;
vector<pair<int, int> > v;
void bfs(pair<int, int> start) {
	q.push(start);
	bor[start.first][start.second] = true;

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (nr < 0 || nc < 0 || nr >= N || nc >= N || bor[nr][nc])
				continue;
			if (abs(m[nr][nc] - m[cur.first][cur.second]) >= L &&
				abs(m[nr][nc] - m[cur.first][cur.second]) <= R) {
				q.push({ nr, nc });
				bor[nr][nc] = true; 
				
				v.push_back({ nr, nc });
				idxSum += m[nr][nc];
			}
		}
	}
}
void init() {
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			bor[i][j] = 0;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> m[i][j];

	int res = 0;
	while (1) {
		updated = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!bor[i][j]) {
					v.clear();
					v.push_back({ i,j }); 
					idxSum = m[i][j];
					bfs({ i, j });
				}
				//열린 국경이 있으면
				if (v.size() >= 2) { //한 연합 내의 국가 개수
					updated = true;
					int val = idxSum / v.size();
					for (int i = 0; i < v.size(); i++) {
						m[v[i].first][v[i].second] = val;
					}
				}
			}
		}
		if (updated) res++;
		else break;
		init();
	}
	cout << res << '\n';
	return 0;
}

https://www.acmicpc.net/problem/17281

선수 9명의 순서를 결정해야 한다. 4번 타자는 1번 선수로 고정되어 있기 때문에 이를 반영해준다.

이닝별로 선수들의 결과를 입력으로 받는다.

따라서 모든 순열을 구해서 선수들의 순서를 만들어낸 이후에, 야구의 조건을 구현해주면 된다.

1루, 2루 등에 진출해 있는 선수들에 대한 관리는, 선수 번호를 그대로 인덱스로 해서 배열을 두었다.

1이면 1루에 있다는 뜻이고, 2면 2루 3이면 3루에, 

4 이상이 되면 홈으로 들어왔다는 의미이다.

각 이닝별로 선수들의 수행을 그대로 따라가면서 시뮬레이션을 진행해주면 된다.

res[][] 배열은 이닝별 선수의 득점이다.

num은 1~9까지 선수들 중에 9명을 뽑는 경우의 수로 사용한다.

ord는 뽑아서 결정된 선수들의 순서이다. ord[i]는 i번 타자를 의미한다.

#include<iostream> //2백만
#include<vector>
using namespace std;
int n, res[52][10], num[10], ord[10], pos[10], Max = -1;
bool isused[10];
void play() {
	int hitter = 1, score = 0;
	for (int i = 1; i <= n; i++) { //i이닝에
		int outCnt = 0;

		while (1) {
			if (res[i][ord[hitter]] == 0) { //아웃인 경우
				hitter++;
				if (hitter >= 10) hitter = 1;
				outCnt++;
				if (outCnt == 3) {
					//이닝 교체
					for (int j = 1; j <= 9; j++) pos[j] = 0;
					break;
				}
			}
			else {
				//득점타
				for (int j = 1; j <= 9; j++) {
					if (pos[j] > 0 || j == ord[hitter]) { //타석에 나가 있는 선수라면
						pos[j] += res[i][ord[hitter]];
						if (pos[j] >= 4) {
							//홈에 들어오면
							pos[j] = 0;
							score++;
						}
					}
				}
				hitter++;
				if (hitter >= 10) hitter = 1;
			}
		}
	}
	if (Max < score) Max = score;
}
void func(int k) {
	if (k > 9) { //base condition
		play();
		return;
	}
	for (int i = 2; i <= 9; i++) {
		if (!isused[i]) {
			ord[k] = i;
			isused[i] = true;
			if (k == 3) func(k + 2); //3번엔 다음 4번이 아니라 5번을 정함
			else func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	for (int i = 1; i <= 9; i++)
		num[i] = i;
	isused[1] = true; //1은 항상 사용중
	ord[4] = 1; // 4번 선수는 항상 1
	cin >> n;
	
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= 9; j++) 
			cin >> res[i][j];
	
	func(1);
	cout << Max << '\n';
	return 0;
}

https://www.acmicpc.net/problem/17144

약간의 bfs와 시뮬레이션이 혼합된 문제이다.

입력을 받은 이후에, 먼지가 있는 곳을 미리 큐에 넣어준다. 동시에 확산되어야 한다는 조건이 있기 때문이다.

미리 큐에 넣어주고, 한 번 탐색을 했을 때 큐의 크기만큼만 확산을 진행하면 단위 시간이 흘렀다고 볼 수 있다.

그리고, 이전에 발생했던 먼지의 확산이, 앞으로 발생하게 될 먼지의 확산에 영향을 끼치지 않게 하기 위해서

변화량을 따로 저장한 이후에, 확산을 마치고 변화량을 모두 구한 이후에 한꺼번에 반영해줘야 한다.

그렇지 않으면 동시에 확산했다는 조건을 만족시킬 수 없기 때문이다.

다음으로 환기에 대한 조건을 구현할 때는, 조건에 맞게 인덱스를 가지고 놀아주면 된다.

한 가지 주의할 사항은, 환기의 순서를 신경 써야 한다는 것이다.

먼저 빨려들어가서 없어지는 먼지의 값을 덮어 씌워주는 방향으로 순서를 정해야, 중간에 다른 구석 지점에서 먼지의 값이 누락되는 것을 방지할 수 있다.

따라서 먼저 빨려들어가는 쪽에 대한 처리를 먼저 해주는 방식으로 구현한다.

#include<iostream>
#include<queue>
using namespace std;
int m[52][52], T, R, C, dif[52][52];
bool vis[52][52];
pair<int, int> Up;
pair<int, int> Dn;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void clean() {
	//상부
	for (int i = 1; i <= Up.first - 1; i++)  //하향
		m[Up.first - i][0] = m[Up.first - 1 - i][0];
	for (int i = 0; i <= C - 2; i++) //좌향
		m[0][i] = m[0][i + 1];
	for (int i = 0; i <= Up.first - 1; i++) //상향
		m[i][C - 1] = m[i + 1][C - 1];
	for (int i = C - 1; i >= 1; i--) //우향
		m[Up.first][i] = m[Up.first][i - 1];


	//하부
	for (int i = Dn.first + 1; i <= R - 2; i++) //상향
		m[i][0] = m[i + 1][0];
	for (int i = 1; i <= C - 1; i++) //좌향
		m[R - 1][i - 1] = m[R - 1][i];
	for (int i = R - 1; i >= Dn.first + 1; i--)//하향
		m[i][C - 1] = m[i - 1][C - 1];

	for (int i = C - 1; i >= 1; i--) //우향
		m[Dn.first][i] = m[Dn.first][i - 1];
}

void bfs() {
	int cnt = q.size();
	while (cnt--) {
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (nr < 0 || nc < 0 || nr >= R || nc >= C ) continue;
			if (nr == Up.first && nc == Up.second) continue;
			if (nr == Dn.first && nc == Dn.second) continue;
			
			dif[cur.first][cur.second] -= m[cur.first][cur.second] / 5;
			dif[nr][nc] += m[cur.first][cur.second] / 5;
		}
	}
	//update
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			m[i][j] += dif[i][j];
		}
	}
	//Print();
	clean();
}
void init() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			vis[i][j] = false;
			dif[i][j] = 0;
		}
	}
}
int main(void) {
	cin >> R >> C >> T;
	bool fst = true;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> m[i][j];
			if (m[i][j] == -1) {
				m[i][j] = 0;
				if (fst) {
					Up.first = i;
					Up.second = j;
					fst = false;
				}
				else {
					Dn.first = i;
					Dn.second = j;
				}
			}
		}
	}
	
	//1초 루틴
	while (T--) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (m[i][j] != 0 && !vis[i][j]) { //방문 조건도 사실 필요없음
					q.push({ i, j });
					vis[i][j] = true;
				}
			}
		}
		bfs();
		init();
	}
	int Sum = 0;
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			Sum += m[i][j];
	cout << Sum << '\n';
	return 0;
}