[백준 11967] 불켜기 (C++) BFS풀이

# 문제링크

www.acmicpc.net/problem/11967

11967번: 불켜기

vector[][]를 만들어서 (x,y)좌표에 있는 스위치 위치를 push 해주었다. (1,1) 좌표부터 시작해서, 

1) 좌표에 있는 스위치 불 켜기

2) 불을 새로 켰으면, 해당 위치부터 다시 BFS 돌리기위해서 visited와 queue 초기화

3) 네 방향으로 탐색하면서 불 켜져있는 곳으로 이동

 

이렇게 진행해줬는데, 한 번 스위치를 켰으면 다음 번에는 또 스위치를 켜 줄 필요가 없다. 따라서 스위치를 켜고 나서 map[x][y] 에 2로 체크를 해주었다. 이후 map이 2이면 스위치 돌리는 걸 안해준다. 

 

특정 좌표에 도착하고나서, visited를 초기화 시켜서 다시 해당 좌표부터 출발하는 문제를 전에 풀어봤었다. 문제를 풀어가면서 점점 전에 풀었던 접근방식이 떠올라서, 문제를 푸는 속도나 정확도가 올라가는 게 느껴지고 뿌듯하다. 그래서 문제를 더 많이 풀지 못한게 더 신경쓰이기도 한다. ㅠ,ㅠ 왤케 게으름을 피우고 문제를 안풀었는지 후회스럽다. 하지만 지나간 일이니 오늘부터라도 정신차리기.. 

 

2021.04.12 - [Computer Science&Engineering/코딩테스트] - [백준 16236] 아기상어 C++

 

 

# 제출 코드 

 

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

bool map[101][101]; // 불 켜기 
bool visited[101][101]; // 방문 여부 
int N, M;
int yd[] = { 1, -1, 0,0 };
int xd[] = { 0,0,1, -1 };
vector <pair<int, int>> v[101][101];

int BFS() {
	int ans = 1;
	queue <pair<int, int>> q;
	q.push({ 1,1 }); // start
	visited[1][1] = true;
	map[1][1] = true;
	bool flag = false;

	while (!q.empty()) {
		flag = false;
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (map[x][y] != 2) {
			for (int i = 0; i < v[x][y].size(); i++) { // 방에 불켜기
				int a = v[x][y][i].first;
				int b = v[x][y][i].second;
				if (map[a][b] == 1) continue;
				map[a][b] = 1;
				ans++; // 불 켜졌다~!
				flag = true;
			}
			map[x][y] = 2; // 불켜기 진행 완료 체크 -> 다음부터 불켜지 마라../ 
		}

		if (flag) {
			memset(visited, 0, sizeof(visited)); // 불 켜진데부터 다시 출발~!
			visited[x][y] = true;
			while (!q.empty()) q.pop();
		}

		for (int i = 0; i < 4; i++) { // 이동 
			int nx = x + xd[i];
			int ny = y + yd[i];
			if (nx <= 0 || nx > N)continue;
			if (ny <= 0 || ny > N)continue;
			if (visited[nx][ny] == true)continue;
			if (map[nx][ny] == 0)continue; // 불꺼져있음 
			visited[nx][ny] = true;
			q.push({ nx, ny });
		}
	}
	return ans;
}
void Input() {
	int x, y, a, b;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d %d", &x, &y, &a, &b);
		v[x][y].push_back({ a,b });
	}
}
int main() {
	Input();
	printf("%d\n", BFS());
}