[BOJ 28291 / C++] 레드스톤

백준 문제 링크 : 28291 - 레드스톤

문제

마인크래프트 고수인 당신은 midori, changwook987과 함께 마인크래프트를 플레이 중이다.

changwook987은 레드스톤 회로 블록들을 이용해
$W×H$ 크기의 사각형 맵에 회로를 만들었다. 회로 블록에는 레드스톤 가루, 레드스톤 블록, 레드스톤 램프가 있다.

• 레드스톤 가루(redstone_dust)는 상하좌우로 인접한 회로 블록에 매초마다 전기 신호를 전달하며, 전달할 회로 블록에 더 큰 전기 신호가 있다면 전달하지 않는다.
• 레드스톤 블록(redstone_block)은 전기 신호를 15만큼 가지고 있으며 상하좌우로 인접한 회로 블록에 15만큼의 전기 신호를 매초마다 전달한다.
• 레드스톤 램프(redstone_lamp)는 1 이상의 전기 신호를 받을 경우 불이 켜진다.
  전기 신호는 회로 블록들이 작동하기 위해 필요한 에너지로 레드스톤 가루(redstone_dust)에서 다른 블록으로 전달될 때 1 감소하며 0 이하가 될 시 사라진다. 또한 여러 전기 신호가 한 블록에 모일 경우 그중 가장 큰 신호가 그 블록의 신호의 세기가 된다.

모든 회로 블록은 여러 번 행동할 수 있으며, 모두 동시에 행동한다.

changwook987은 midori에게 이 회로에 있는 모든 레드스톤 램프가 켜지는 순간이 있는지 알아보는 프로그램을 만들어 달라고 한다.

마인크래프트 초보인 midori는 당신에게 도움을 요청했다. midori를 도와 프로그램을 작성해 주자.

입력

첫째 줄에는 맵의 가로 길이
$W$와 세로 길이
$H$가 정수로 주어진다.
$(1 \le W,H \le 50)$ 

둘째 줄에는 회로 블록의 개수
$N$이 정수로 주어진다.
$(1 \le N \le W×H)$ 

셋째 줄부터
$N$개의 줄에는 회로 블록의 타입
$B$ ("redstone_dust", "redstone_block", "redstone_lamp" 중 하나)와 회로 블록의 가로 위치
$X$, 세로 위치
$Y$가 정수로 주어진다.
$(0 \le X \le W-1; 0 \le Y \le H-1)$ 

또한 입력으로 주어지는 회로 블록에는 "redstone_lamp"가 하나 이상 포함되어 있다.

출력

모든 레드스톤 램프가 켜지는 순간이 존재하면 "success", 모든 레드스톤 램프가 켜지는 순간이 존재하지 않는다면 "failed"를 출력한다.

입출력 예시

문제를 대충 보면 틀리기 십상인 문제같습니다. 저도 문제를 살짝 잘못 이해해서 몇 번 틀렸네요.
실제 마인크래프트가 이렇게 동작하는지 모르겠네요.. 마인크래프트 나름 해봤다고 생각했는데 ㅋㅋㅎ;

풀이

가장 먼저, 맵의 모든 블럭을 -1로 초기화하고, n개의 회로블럭들을 입력받을 때는 가루칸은 0, 블록칸은 15, 램프칸은 -2로 합니다. 또한, 블록칸 좌표를 담는 queue, 그리고 램프칸 좌표를 담는 queue를 각각 유지하여 나중에 꺼내먹을 수 있도록 합니다. 가루칸은 나중에 신호의 강도를 값으로 가지게 됩니다.

• 맵의 좌표가 갖는 값은, 일반 칸은 -1 / 가루 칸은 0~15 / 블록 칸은 15 / 램프 칸은 -2.

램프 칸을 -2로 두는 이유는, 레드스톤 램프는 레드스톤 신호를 전달하지 못하기 때문에, 회로 블럭이 아닌 경우와 비슷한 취급을 하고자 -2로 두었습니다.

이제 n개의 회로블럭에 대한 입력이 끝났다면, 다음 과정을 통해 레드스톤 램프들이 모두 켜질 수 있는지 확인하도록 합니다.

1. 레드스톤 블럭들의 좌표를 queue에서 하나씩 꺼내어, 깊이우선탐색(DFS)를 시행하며 연결된 레드스톤 가루들에 대해 신호를 전달합니다.
   이 때 주의할 점은, "레드스톤 블럭은 주변 회로블럭에 15의 강도를 전달합니다"라는 말이 있었으므로, 레드스톤 주변의 회로블럭은 강도가 14가 아닌 15가 되어야 합니다.
   또한, 신호가 한 블럭에 모일 경우 가장 큰 신호가 해당 블럭의 신호 세기가 되므로, 방문여부를 확인할 때 신호의 강도를 또한 확인하도록 합니다.

2. 이제 레드스톤 가루들에 신호가 전해졌으므로, 램프를 확인한다. 램프들의 좌표를 queue에서 하나씩 꺼내어, 인접 좌표의 신호가 2 이상인지 확인하고, 4칸 모두 신호가 1 이하인 경우 램프가 켜지지 못하므로, failed를 출력 후 종료한다.
   이 때 주의할 점은, 레드스톤 램프의 인접한 회로블럭에는 신호가 2 이상 흘러야 한다는 점이다. 인접한 회로블럭의 신호 강도가 1이라면, 램프에는 0이 들어오기 때문에 2 이상의 신호가 인접 회로블럭에 흘러야한다.

정리

레드스톤 블럭에서부터 DFS를 수행하며 레드스톤 가루들이 어느정도의 신호강도를 갖는지 입력한 뒤, 레드스톤 램프들의 인접 좌표의 신호 강도를 확인한다.

주의 :

• 레드스톤 블럭은 인접 회로블럭에 15의 세기를 전달한다. 블럭 상하좌우에는 강도가 14가 아닌 15
• 레드스톤 램프는 레드스톤 신호를 전달하지 않음.
• 여러 신호가 한 블럭에 모이는 경우 그 신호들 중 가장 큰 신호의 세기가 해당 블럭의 신호 세기임.
• 레드스톤 램프의 인접 좌표는 2 이상의 값이 있어야 램프가 켜질 수 있음. 그래야 램프에는 1 이상의 신호가 들어오기 때문

레드스톤 램프는 레드스톤 신호를 전달하지 못함을 확인하는 반례

4 4
4
redstone_block 0 0
redstone_lamp 1 0
redstone_dust 2 0
redstone_lamp 3 0

이 경우 정답출력은 failed

또한 레드스톤 블럭에서부터 신호가 어디까지 가는지 확인하실 때는 문제의 예제 입력 4를 적당히 바꿔가며 확인하시면 편리합니다

코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

queue< pair<int,int> >lamp; 
queue< pair<int,int> >block; //큐의 first, second는 각각 x,y좌표임
int map[51][51];
int visited[51][51];
int w, h, n;

void dfs(int y, int x, int cnt) {
	if (x < 0 || y < 0 || x >= w || y >= h || cnt <= 0 || map[y][x] <= -1) return;
	//맵 밖을 벗어났거나, 더이상 신호의 강도(cnt)가 남지 않았거나, 해당 좌표가 회로블럭이 아닌 경우(-1)
	if (visited[y][x] >= cnt) return; //또한 이미 방문했고 현재 cnt가 더 크지 않은 경우 
	visited[y][x] = cnt;
	map[y][x] = cnt;
	dfs(y+1, x, cnt-1);
	dfs(y, x+1, cnt-1);
	dfs(y-1, x, cnt-1);
	dfs(y, x-1, cnt-1);
}

bool isOn(int y, int x) {
	if (x < 0 || y < 0 || x >= w || y >= h) return false;
	if (map[y][x] >= 2) return true;
	else return false;
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> w >> h;
	cin >> n;
	for(int i=0;i<h;i++) {
		for(int j=0;j<w;j++) {
			map[i][j] = -1;
		}
	}
	for(int i=0;i<n;i++) {
		string in;
		int x, y;
		cin >> in >> x >> y;
		if (in == "redstone_dust") {
			map[y][x] = 0;
		}
		if (in == "redstone_block") {
			map[y][x] = 15;
			block.push(make_pair(y,x));
		}
		if (in == "redstone_lamp") {
			map[y][x] = -2;
			lamp.push(make_pair(y,x));
		}
	}


	while (block.size()) {
		pair<int,int>tmp = block.front();
		block.pop();
		visited[tmp.first][tmp.second] = 15;
		dfs(tmp.first+1, tmp.second, 15);
		dfs(tmp.first-1, tmp.second, 15);
		dfs(tmp.first, tmp.second+1, 15);
		dfs(tmp.first, tmp.second-1, 15);
	}
	while (lamp.size()) {
		pair<int,int>tmp = lamp.front();
		lamp.pop();
		if (!isOn(tmp.first+1, tmp.second) && \
			!isOn(tmp.first, tmp.second+1) && \
			!isOn(tmp.first-1, tmp.second) && \
			!isOn(tmp.first, tmp.second-1)) {
				cout << "failed";
				return 0;
			}
	}
	cout << "success";
}