[BOJ/백준 11967/C++] 불켜기

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)방의 불을 켜고 끌 수 있다는 의미이다.

- 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

- 시간 제한 : 2초

- 메모리 제한 : 512MB

 

[문제 풀이]

필자는 다음과 같은 순서로 문제를 생각해보았다.

• 한 방에 여러개의 스위치가 있을 수 있음으로, 2차원배열에 원소는 vector<pair<int,int>>의 형태로 각 방별 스위치 정보를 저장한다.
• 불이 켜져있고, 연결되어 있고 이미 지나온 방에 한해서 이동이 자유롭다고 생각한다.
• 원소가 pair<int,int> 인 1차원 vector Remain 과 Use를 이용해 현재 상태에서 갈 수 있는 방과 불이켜져있고 현재상태에서 인접하게 이동가능 한 방을 나누어 생각한다.
• Use를 확인하면서 추가적으로 현재 상태에서 갈 수 있는 방을 remain에 추가
• 3~4과정을 반복하면서 변화가 없으면 종료

위처럼 생각했는데 한번 그림으로 알아보자

 

먼저 문제에서 주어진 예제를 다음과 같이 데이터를 저장한다.

1행 1열에는 1행2열, 1행3열의 불을 킬 수 있는 스위치가 있다라고 표시한 것이다.

마찬가지로 1행 3열에는 1행2열, 2행1열의 불을 킬 수 있는 스위치가 있다는 것이다.

 

다음으로 문제에서 이동은 1행 1열 부터 시작한다고 했으니 1행 1열부터 시작해보면

맨 처음에 (1,1)을 방문하면 (1,2)와 (1,3)의 불이 켜지게 된다. 그 다음 (1,1)은 불을 켜는데 사용했고 방문도 했으니 use 배열에 넣어주고, use배열의 크기만큼 상하좌우 인접한 칸들을 remain에 넣어준다.

이때 remain이 하는 역할은 아직 불이 켜지지 않은 방에 대해서도 나중에 그 방에 불이 켜질 수도 있기 때문에 저장해놓는 배열이다.

 

remain에 있는 좌표들을 확인하면서 불이 켜진 방에 대해서는 그 방으로 이동할 수 있다면 이동하고, 아직 이동이 안된다면 계속 remain에 남겨두는 방식인 것이다.

 

(1,2)에는 스위치가 없다.

위의 remain에서 불이 켜져 있는 방은 (1,3)밖에 없으므로 use에 (1,3)만 넣어준다.

 

바로 위의 경우에서 remain에는 더 이상 불이 켜져 있는 방이 남아있지 않다. 이때 break걸어주고 여태까지 방에 불을 켤때 cnt 변수를 이용해 하나씩 증가시키면서 불을 켜왔던 방의 개수를 구할 수 있다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int n, m;
int dx[4] = { 1, 0 , -1 , 0 };
int dy[4] = { 0, 1, 0 , -1 };
vector<vector<vector<pii>>> dt;
vector<vector<bool>> ck;
vector<vector<bool>> light;

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

	cin >> n >> m;
	dt.resize(n + 1); ck.resize(n + 1); light.resize(n + 1);
	for (int i = 0; i < n + 1; i++) ck[i].resize(n+1);
	for (int i = 0; i < n + 1; i++) dt[i].resize(n+1);
	for (int i = 0; i < n + 1; i++) light[i].resize(n + 1);

	for (int i = 0; i < m; i++)
	{
		int srow, scol, erow, ecol;
		cin >> srow >> scol >> erow >> ecol;
		dt[srow][scol].push_back({ erow,ecol });
	}

	int cnt = 1;
	vector<pii> q;
	q.push_back({ 1,1 });
	light[1][1] = true; ck[1][1] = true;
	while (1)
	{
		vector<pii> remain;
		vector<pii> use;
		bool flag = false;
		for (int i = 0; i < q.size(); i++)
		{
			int row = q[i].first; int col = q[i].second;
			if (!light[row][col]) { remain.push_back({row,col}); continue; }

			flag = true;
			for (int j = 0; j < dt[row][col].size(); j++)
			{
				int sw_row = dt[row][col][j].first;
				int sw_col = dt[row][col][j].second;

				if (!light[sw_row][sw_col])
				{
					light[sw_row][sw_col] = true;
					cnt++;
				}
			}
			use.push_back({ row,col });
		}
		if (!flag) break;
		for (int i = 0; i < use.size(); i++)
		{
			int row = use[i].first; int col = use[i].second;

			for (int j = 0; j < 4; j++)
			{
				int nx = col + dx[j];
				int ny = row + dy[j];

				if (nx < 1 || ny < 1 || ny > n || nx > n) continue;
				if (ck[ny][nx]) continue;

				ck[ny][nx] = true;

				remain.push_back({ ny,nx });
			}
		}
		q.clear();
		q = remain;
	}
	cout << cnt;
}

약간 난해하게 설명한 부분도 있는 것 같은데

https://tobrother.tistory.com/53

[프로그래머스/Level 3/C++/2022 카카오 블라인드 채용] 양과 늑대

이 문제 풀이법을 약간 응용해서 풀었다고 보면 된다.

굳