[백준 11967] 불켜기

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

11967번: 불켜기

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;

struct _st
{
	int x;
	int y;
};

vector<_st> ROOM[100 + 2][100 + 2];
queue<_st> Q;
int visited[100 + 2][100 + 2];
int lights[100 + 2][100 + 2];

void debug()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%d ", lights[i][j]);
		}
		printf("\n");
	}
}


void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int x = 0, y = 0, a = 0, b = 0;
		scanf("%d %d %d %d", &x, &y, &a, &b);
		ROOM[x][y].push_back({ a, b });	// (x, y)좌표에서 (a, b) 불 켤 수있음 
	}
}

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




int BFS()
{
	// 방문배열 초기화
	init();

	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	int cnt = 0;
	Q = {};				// BFS 여러번 돌림, 큐 초기화
	Q.push({ 1, 1 });	// 항상 (1, 1) 부터 시작
	visited[1][1] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N  || ny < 1 || ny > N ) continue;
			if (lights[nx][ny] == 0) continue;
			if (visited[nx][ny]) continue;
			visited[nx][ny] = 1;
			Q.push({ nx, ny });
		}

		if (ROOM[data.x][data.y].size() != 0) {		// 해당 좌표에 스위치가 존재하다면 켜준다 
			for (_st sw : ROOM[data.x][data.y]) {
				if (lights[sw.x][sw.y]) continue;	// 이미 켜져있는 곳이면 스루
				lights[sw.x][sw.y] = 1;
				cnt++;
			}
		}
		ROOM[data.x][data.y].clear();

	}
	return cnt;
}



int turn_on()
{
	int total = 1;	// (1, 1)은 항상 불이 켜져있음 
	lights[1][1] = 1;	// 유일하게 불이 켜져있는 방
	for (_st sw : ROOM[1][1]) {
		if (lights[sw.x][sw.y]) continue;	// 이미 켜져있는 곳이면 스루
		lights[sw.x][sw.y] = 1;
		total++;
	}
	ROOM[1][1].clear();		// (1, 1) 에서 켤 수 있는 방 다 켰음 

	// 이 문제는 좌표를 기준으로 탐색하는게 아니라
	// 돌릴때 마다 맵을 탐색하면서 불을 또 켤 수 있는지를 봐야한다. 
	while (1) {
		int tmp = BFS();
		if (tmp == 0) return total;
		total += tmp;
	}
}



int main()
{
	input();
	int ans = turn_on();
	//debug();
	printf("%d\n", ans);
	return 0;
}

드디어.. 불켰다... 

존의 암소샠키들... 내가 언젠가 암살하러 감..

 

 

내가 주의했어야 할 몇 가지 사항은 다음과 같다. 

1. 처음에 이중루프로 맵 전체를 스캐닝하면서 BFS를 돌리는 코드로 짰다(5% 컷 ㅋ). 그런데 이렇게 구현하면 만약 (1, 2) 좌표의 불이 (3, 3)에서 켜졌다면, 다시 후진을 못한다. 벌써 루프의 i, j 인덱스가 3, 3까지 진행되어 버렸기 때문이다. 

따라서 이 문제는 while문으로 BFS를 매번 호출하여 처음부터 다시 맵 전체를 탐색해 주어야 한다. 

2. 그렇다면 while 문은 언제 종료할 수 있을까 ? 

BFS로 맵을 탐색하는데, 갈 수 있는 위치에서 더이상 켤 수 있는 불이 없다면 루프를 종료한다. 

3. 한 방에 여러 개의 스위치가 있을 수 있다. 

즉, (x, y) 좌표에 (a, b)칸의 불을 켤 수 있는 스위치가 존재한다고 하여, 이미 켜져있는 방의 불을 또 킨다면 중복으로 집계가 된다. 따라서 이미 켜져있는 방의 불은 집계 대상에서 제외해야 한다. 

 

// turn_on ( ) 함수

1, 2 번의 주의사항이 구현되어 있는 코드이다. 

(1, 1)의 좌표는 유일하게 불이 켜져있으므로, BFS로 맵을 탐색하기 전에 해당 칸에서 불을 켤 수 있는 칸들을 모두 켜준다.  이때 3.번 주의사항에서 "한 방에 여러 개의 스위치가 있을 수 있다"고 했으므로 if (lights[sw.x][sw.y]) continue; 조건문을 통해 이미 불이 켜져있는 곳이면 무시한다. (이 조건 안쓰면 66% 컷ㅋ... 인생)

그리고 (1, 1) 위치에서 불을 켤 수 있는 방을 모두 켰다면 해당 좌표에 저장된 스위치 정보를 모두 삭제해준다(ROOM[1][1].clear()). 

 

 

// BFS( ) 함수

기존 BFS와 유사하다. 

다만 항상 (1, 1)에서부터 탐색을 시작하고, 여러번 호출되기 때문에 방문배열과 큐를 초기화해주는 것을 잊으면 안된다. 아직 방문하지 않았고, 불이 켜져있는 칸들을 이동한다. 만약 큐에서 pop된 좌표 (data.x, data.y)에 다른 방의 불을 켤 수 있는 스위치가 존재한다면, 이미 켜져있는 곳을 제외하고 불을 키면서 cnt 변수의 값을 증가시킨다. 

만약 cnt 변수의 값이 더이상 증가하지 않는다면, 불이 켜져있으면서 방문할 수 있는 칸을 모두 방문했는데 더 이상 켤 수 있는 방이 없다는 뜻이므로 0을 리턴하고, turn_on( ) 함수에서 루프를 빠져나오게 된다. 

 

 

---

++22.10.31 다시 풀었다. 

Flood-Fill 시, 좌표 기준이 아니라 "현재 상태에서 더 상태 발전이 가능한지(불 켤 수 있으면 발전, 더 이상 켤 불이 없으면 종료)"를 기준으로 루프를 돌리는 문제. 

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
int N, M;	// N 격자 크기, M 스위치 개수

struct _st
{
	int r, c;	// 각 격자 칸에서의 스위치 정보 
};

std::vector<_st> board[100 + 2][100 + 2];
int lights_on[100 + 2][100 + 2];
std::queue<_st> Q;
int visited[100 + 2][100 + 2];


void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int x = 0, y = 0, a = 0, b = 0;
		scanf("%d %d %d %d", &x, &y, &a, &b);
		board[x][y].push_back({ a, b });
	}
}

bool turn_on_lights()
{
	static int dir_x[4] = { 0, 0 ,1 ,-1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	Q = {};
	memset(visited, 0, sizeof(visited));
	bool new_on = false;

	Q.push({ 1, 1 });
	visited[1][1] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.r + dir_x[p];
			int ny = data.c + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (lights_on[nx][ny] == 0) continue;
			if (visited[nx][ny]) continue;
			if (!board[nx][ny].empty()) {
				for (_st v : board[nx][ny]) {
					if (lights_on[v.r][v.c]) continue;
					lights_on[v.r][v.c] = 1;
					new_on = true;
				}
				board[nx][ny].clear();	// 한 번 방문해서 불 켠 방은 스루하려고 
			}
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
	return new_on;	// /끝까지 다 돌려야 한다 !
}




void Flood_Fill()
{
	// (1, 1) 에서 켤 수 있는 칸 켜기
	lights_on[1][1] = 1;
	if (!board[1][1].empty()) {
		for (_st v : board[1][1]) {
			lights_on[v.r][v.c] = 1;
		}
	}
	board[1][1].clear();

	// 탐색
	while (1) {
		if (!turn_on_lights()) return;
	}
}


int output()
{
	int on = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (lights_on[i][j] == 1) on++;
		}
	} 
	return on;
}



int main()
{
	input();
	Flood_Fill();
	int ans = output();
	printf("%d\n", ans);
	return 0;
}