[BOJ] 백준 11967번 : 불켜기 C++ : 아주정은

이 문제는 런타임에러, 메모리초과, 컴파일에러가 정말 많이 발생했다.

비주얼 스튜디오에서는 돌아가는데 백준서버에서는 돌아가지 않았다.

처음에 어느 지점에서 다른 지점의 불을 켤 수 있는 숫자를 받을때, 이것을 어떻게 저장해야할까 고민을 많이 했다.

그래서 3차원 배열을 사용하기로 하였다. 근데 문제는 숫자가 2만개까지 가능하기에 배열 크기가 너무 커져서

런타임 에러가 발생했다. 그래서 구글링.....

구글링을 해보니 다른사람은 vector를 썻더라.... 벡터는 좋다고는 들었지만, 안보에 있어서 나는 보수이기 때문에..... 쉽게 받아들이고 싶지 않았다. 하지만 계속되는 메모리초과와 런타임에러로 나는 벡터를 수용했다.

서론은 여기까지고, 이문제는 1,1은 항상 불이 켜져있다. 그래서 1,1에서 켤수있는 불들을 일단 켜준다.

그다음 상하좌우를 살피고 갈수있는곳을 간다. 그리고 거기서 새로운 불을 켠다면, 다시 1,1부터 BFS를 통해 배열을 돈다.

음 BFS를 여러번하는거는 시간이 그렇게 많이 들지는 않나보다?라는 생각을 했다.

암튼 교훈은 vector 사용하자. 여러 함수 알아놓자. 입니다.

신문물 받아들입시다!

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

using namespace std;

struct Que {
	int x;
	int y;
};

//Que board[101][101][20001];

vector<Que> board[101][101];
bool light[101][101];
bool vis[101][101];

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

int main()
{
	int N, M;
	int a, b, c, d;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c >> d;
		board[a - 1][b - 1].push_back({c-1,d-1});
	}

	while (1) {
		memset(vis, false, sizeof(vis));//cstring헤터 필요 vis를 초기화
		queue<Que> Q;
		Q.push({ 0,0 });//(0,0)부터 시작하기 때문에
		vis[0][0] = true;
		light[0][0] = true;//불 계속켜주는건 비효율이지만 어쩔수없음
		bool flag = false;
		while (!Q.empty()) {
			auto cur = Q.front();
			Q.pop();
			if (!board[cur.x][cur.y].empty()) {
				for (int i = 0; i < board[cur.x][cur.y].size(); i++) {
					auto c = board[cur.x][cur.y][i];
					light[c.x][c.y] = true;
				}//불을 켜준다.
				board[cur.x][cur.y].clear();//불을 켜준뒤 벡터에 남아있는거 없앤다.
				flag = true;//새로운방에 불을 켰다는 의미
			}

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx<0 or nx>N - 1 or ny<0 or ny>N - 1)continue;
				if (light[nx][ny] == true and vis[nx][ny] == false) {
					Q.push({ nx,ny });
					vis[nx][ny] = true;
				}
			}//상하좌우 돌면서 불켜진방 탐색
		}
		if (!flag) {
			break;
		}//새롭게 불켜진방이없으면 break
	}
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (light[i][j])cnt++;
		}
	}//불켜진방 갯수 세보자.
	cout << cnt << endl;
}