백준 BOJ 11967 - 불켜기

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

11967번: 불켜기

BFS 응용

pair<int,int> 로 좌표를 관리해줘도 되는데,

나는 그냥 편의상 x*1000+y 로 묶어서

1차원 배열로 만들어서 BFS를 돌려주었다.

 

불을 켜는 경우와 실제로 탐색하는 경우를 분리해줘야 하는데,

이를 위해서 방문체크를 위한 vis배열과

불이 켜져있는지 체크를 위한 light 배열 두개를 만들어서 각각 관리해줬다.

 

프로그램 작성 과정에서도

불을 켜는걸 항상 우선시 한 뒤에

실제로 탐색하도록 작성해야 한다.

 

이때, 불이 늦게 켜져서 새로 탐색 가능해지는 경우가 있으므로

불을 켤때 켜진 불 주변으로 이미 탐색했던 적이 있는 방이 있다면

불을 켠 방의 좌표도 다시 큐에 넣어주어야 전부 탐색이 가능하다.

 

#include <bits/stdc++.h>
using namespace std;

vector<int> g[1000000];
bool vis[1234567] = {0};
bool light[1234567] = {0};

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

int N,M;

int bfs(){
	queue<int> q;
	q.push(1001);
	vis[1001] = true;
	light[1001] = true;
	
	while(!q.empty()){
		int now = q.front();
		q.pop();
		
		for(int nxt : g[now]){
			if(!light[nxt]){
				light[nxt] = true;
				
				for(int i=0; i<4; i++){
					int nnxt = nxt + 1000*dx[i] + dy[i];
					
					int x = nxt/1000;
					int y = nxt%1000;
					if(x==0 || x==N+1 || y==0 || y==N+1) continue;
					
					if(vis[nnxt]) q.push(nnxt);
				}
			}
		}
		
		for(int i=0; i<4; i++){
			int nxt = now + 1000*dx[i] + dy[i];
			
			int x = nxt/1000;
			int y = nxt%1000;
			if(x==0 || x==N+1 || y==0 || y==N+1) continue;
			
			if(light[nxt] && !vis[nxt]){
				q.push(nxt);
				vis[nxt] = 1;
			}
		}
	}
	
	int ans = 0;
	for(int i=0; i<1234567; i++) ans += light[i];
	return ans;
}

int main(){
	int a,b,c,d;
	cin >> N >> M;
	for(int i=0; i<M; i++){
		cin >> a >> b >> c >> d;
		g[a*1000+b].push_back(c*1000+d);
	}
	
	cout << bfs();
	return 0;
}