[C/C++] 백준 - 11967번 : 불켜기

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

11967번: 불켜기

문제

농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2≤N≤100)과, M(1≤M≤20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다. 

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

 

< 문제 설명 >

(1,1)부터 시작해서 그 칸에 존재하는 다른방 스위츠를 눌러 불을 켜준다. 

그리고 불을 다 켰으면 이동을 시작하는데 이동은 인접한 칸 중 불이 켜져있는 곳으로만 가능하다.

최대 불을 몇개까지 킬 수 있는지 구하는 문제이다.

 

위 문제 설명만 보면 정말 쉬워보인다. 하지만 까다로운 부분이 하나 존재한다.

그래프 탐색에서 방문처리를 하지 않으면 계속 같은 위치만 반복하여 이동할 수 있기 때문에 매우 비효율적이다.

그렇기 때문에 그래프 탐색을 진행하면서 방문처리를 하고 방문한 곳은 재방문 하지 않도록 하는데 위 문제를 그렇게 풀고자 한다면 전에는 가지 못했던 구역이지만 새롭게 불이 켜져 갈 수 있는 구역들을 재방문 했던 곳에 의해 더 이상 진행을 할 수 없어 결국에는 방문할 수 없게 된다.

 

이 문제에서 신경 써야할 부분이 난 이 부분밖에 없다고 생각이 되었다. 

처음에 BFS로 해결하려했으나 위에 적은 그대로의 문제가 발생하였고, 다른 해결방안을 생각해보아야 했다.

 

나는 BFS가 아닌 DFS를 통해 해결하고자 하였다. 해결과정은

1. (1,1)이 시작지점이므로 (1,1)에 존재하는 스위치들을 모두 켜준다. 그리고 출발 지점은 당연히 (1,1)이 된다

2. (1,1)에서 시작해서 갈 수 있는 구역으로 DFS를 진행한다. DFS를 진행하면서 지나는 경로에 존재하는 스위치는 모두 켜준다. 만약 스위치를 더 이상 켤 수 없다면? 더 이상 갈 수 있는 공간이 존재하지 않다는 뜻이므로 종료시켜준다.

3. DFS가 끝났을 때 마지막 좌표를 저장해준다. 이제 그 곳에서 DFS를 시작해주는 것이다. 방문처리 또한 다시 초기화 시켜준다.

4. DFS 진행의 장점은 갈 수 있는 모든 구역은 깊이 우선 탐색으로 모두 다 돌고 나오기 때문에 결국 한 번 시작해서 스위치를 하나도 켜지 못한다면 더 이상 진행할 필요가 없다는 의미이다. DFS의 위 특성을 이용하여 문제를 해결할 수 있었다.

 

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>

using namespace std;

int N, M, Cnt=1;
bool visited[101][101], isCan;
int board[101][101];
vector<pair<int, int>> Switch[101][101];
pair<int, int> ps;

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

int isValid(int y, int x) {
	return (1 <= y && y <= N && 1 <= x && x <= N);
}

void DFS(int y, int x) {
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (isValid(ny, nx)) {
			if (!visited[ny][nx] && board[ny][nx] == 0) {
				//cout << "다음 : [ " << ny << "." << nx << " ]" << endl;
				visited[ny][nx] = true;
				ps.first = ny, ps.second = nx;
				for (int j = 0; j < Switch[ny][nx].size(); j++) {
					pair<int, int> Cur = Switch[ny][nx][j];
					if (board[Cur.first][Cur.second] == -1) {
						//cout << "새로 불 키는 곳 : [ " << Cur.first << "," << Cur.second << " ]" << endl;
						isCan = true;
						Cnt++;
						board[Cur.first][Cur.second] = 0;
					}
				}
				DFS(ny, nx);
			}
		}
	}
}

void go() {
	memset(board, -1, sizeof(board));
	for (int i = 0; i < Switch[1][1].size(); i++) {
		pair<int, int> Cur = Switch[1][1][i];
		if (board[Cur.first][Cur.second] == -1) {
			//cout << "새로 불 키는 곳 : [ " << Cur.first << "," << Cur.second << " ]" << endl;
			Cnt++;
			board[Cur.first][Cur.second] = 0;
		}
	}
	board[1][1] = 0;
	visited[1][1] = true;
	int y = 1, x = 1;
	while (1) {
		isCan = false;
		//cout << "시작노드 좌표 : [ " << y << "," << x << " ]" << endl;
		DFS(y, x);
		y = ps.first;
		x = ps.second;
		if (!isCan) break;
		memset(visited, false, sizeof(visited));
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		Switch[a][b].push_back({ c,d });
	}
	go();
	cout << Cnt << endl;

	return 0;
}