[백준 11967] 불켜기 c++ (완전 탐색)

문제 링크

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

11967번: 불켜기

 

문제 풀이

우선 간단하게 생각하면, 방에 도착하고, 해당 방 내에 있는 스위치를 통해 가능한 모든 방의 불을 키면서 나아가면 된다.

하지만, 아래와 같은 경우에 주의해야한다.

 

Q)만약 bfs를 돌다가 불이 꺼진 방에 도착해서 그 지점의 탐색을 종료했는데, 이후에 불이 켜져서 도달 가능해진다면?

따라서, BFS를 통해 불이 켜진 방을 탐색하며 해당 방의 스위치를 통해 불을 키는 과정에서, 만약 과거의 탐색 경로에 있었던 방에 불이 켜졌다면, 해당 방에서 탐색을 다시 진행해야한다.

 

나는 이를 위해 3가지 배열을 사용했다.

1) visit: 도착한 모든 방

2) arrive: 불이 켜지고 꺼지고 관계 없이, '도착 가능한' 모든 방

3) light: 해당 방의 불이 꺼졌는가, 켜졌는가.

 

bfs로 각 방에 도착하면 해당 방에 있는 스위치를 통해 킬 수 있는 모든 방의 light[][] 배열에 표시하고, 만약 내가 이전에 도착가능한데, 불이 꺼져 가지 못했던 방( !visit[][] && arrive[][] ) 이 있다면 Queue에 새롭게 추가하여 해당 방을 통한 탐색을 이어나가면 된다. 

 

주의
이 문제에서 가장 주의해야할 부분은 "방문 가능한 불이켜진 방의 수" 가 아닌, "켤 수 있는 불의 수" 라는 점이다.
이 것을 잘못 보고 계속해서 '도달 할 수 있는 방의 수' 를 출력해서 오답이 나왔었다..

 

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
//33분 까지 
vector<pair<int, int>> arr[101][101];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
int light[101][101];// 불 켜진 방 표시 
int visit[101][101];// 실제 방문 (불 켜짐) 
int arrive[101][101];//해당 방 도착 가능(불 꺼져서 못들어간 경우)
int main() {
	int N,M;
	cin >> N >> M;
	int x, y, a, b;
	int answer = 0;
	for (int i = 0; i < M; i++) {
		cin >> x >> y >> a >> b;
		//x,y 이후에나 a,b 도달 가능
		//단, 그 중 1개만 해도 불켜지므로 위상 정렬 x 
		arr[y][x].push_back({ b,a });
	}

	queue<pair<int, int>> qu;
	qu.push({ 1,1 });
	visit[1][1] = 1;
	light[1][1] = 1;
	arrive[1][1] = 1;
	answer++; //켜진 불의 개수!!! 따라서 light가 0-> 1 로 켜질때마다 +1
	
	while (!qu.empty()) {
		int r = qu.front().first, c = qu.front().second;
		//cout << c << ", " << r << endl;
		qu.pop();
		pair<int, int> switch_room;

		//불이 꺼져있다면 키고, 
		//이미 이전에 방문 가능했지만, 불이 꺼져 도달 못했던 방을 추가
		for (int i = 0; i < arr[r][c].size(); i++) {
			switch_room = arr[r][c][i];
			//이미 불이켜져있다면 무시.
			if (light[switch_room.first][switch_room.second] == 1)continue;
			light[switch_room.first][switch_room.second] = 1;
			answer++;

			//이미 이전에 방문 가능했지만, 불이 꺼져 도달 못했던 방을 추가
			if (arrive[switch_room.first][switch_room.second] == 1&&
				visit[switch_room.first][switch_room.second] != 1)
				qu.push({ switch_room.first ,switch_room.second });
		}

		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d], nc = c + dc[d];
			if (1 > nr || nr > N || 1 > nc || nc > N)continue;
			if (visit[nr][nc])continue;
			arrive[nr][nc] = 1;
			if (light[nr][nc] != 1)continue;
			visit[nr][nc] = 1;
			qu.push({ nr,nc });
		}
	}
	cout << answer;
}