c언어 28291번 레드스톤 (백준)

#include <stdio.h>

int w=0, h=0, n=0; //크기를 지칭하는 배열 및, 회로개수

typedef struct A { //구조체
	char x;
	char y;	
}A;

int f(int x, int y) { //범위를 넘어가면 false 아니면 true
	return (x >= 0 && x < w && y >= 0 && y < h);
}

int main(void) {
	scanf("%d %d", &w, &h); //크기 입력
	scanf("%d", &n); //회로 개수 입력
	
	A map[50][50] = {}; //맵에 있는 회로의 종류 (없으면 0, 0)
	A q[34000] = {}; //queue
	int qLeft = 0, qRight=0; //큐 왼쪽, 오른쪽
	A lamp[2500] = {}; //lamp의 위치를 저장하는 구조체 배열
	int lampCnt = 0; //lamp의 개수
	
	for(int i=0; i<n; i++) { //회로 정보 입력 받기
		char s[15];
		int a, b;
		scanf("%s %d %d", s, &a, &b);
		
		if(s[9] == 'b') { //레드스톤 블록
			s[9] = 1;
			map[a][b].y = 16;
            //블록은 큐에 저장
			q[qRight].x = a;
			q[qRight++].y = b;
		}
		else if(s[9] == 'd') s[9] = 2; //레드스톤 가루
		else if(s[9] == 'l') { //레드스톤 램프
			s[9] = 3;
            //램프는 램프를 저장하는 배열에 저장
			lamp[lampCnt].x = a;
			lamp[lampCnt++].y = b;
		}
		map[a][b].x = s[9]; //특정위치에 있는 레드스톤 회로의 정보를 수정
	}
	
	while(qLeft < qRight) { //BFS
		A tmp = q[qLeft++];
		A now = map[tmp.x][tmp.y];
	
		if(now.x != 3 && now.y > 1) { //지금 큐에서 꺼낸 것이 레드스톤 램프가 아니고, 전기 신호가 1 초과임
		if(f(tmp.x+1, tmp.y)) { //아래
			A tmp2 = map[tmp.x+1][tmp.y];
			if(tmp2.y < now.y-1 && tmp2.x > 0) { //또한 아래에 회로가 존재해야 하며, 전기신호가 지금 큐에서 꺼낸 것에 1을 감소한 것보다 더 약하면 탐색을 한다.
				q[qRight].x = tmp.x+1;
				q[qRight++].y = tmp.y; 
				map[tmp.x+1][tmp.y].y = now.y-1;
			}
		}
		if(f(tmp.x-1, tmp.y)) { //위
			A tmp2 = map[tmp.x-1][tmp.y];
			if(tmp2.y < now.y-1 && tmp2.x > 0) { //또한 위에 회로가 존재해야 하며, 전기신호가 지금 큐에서 꺼낸 것에 1을 감소한 것보다 더 약하면 탐색을 한다.
				q[qRight].x = tmp.x-1;
				q[qRight++].y = tmp.y; 
				map[tmp.x-1][tmp.y].y = now.y-1;
			}
		}
		if(f(tmp.x, tmp.y+1)) { //오른쪽
			A tmp2 = map[tmp.x][tmp.y+1];
			if(tmp2.y < now.y-1 && tmp2.x>0) { //또한 오른쪽에 회로가 존재해야 하며, 전기신호가 지금 큐에서 꺼낸 것에 1을 감소한 것보다 더 약하면 탐색을 한다.
				q[qRight].x = tmp.x;
				q[qRight++].y = tmp.y+1;
				map[tmp.x][tmp.y+1].y = now.y-1;
			}
		}
		if(f(tmp.x, tmp.y-1)) { //왼쪽
			A tmp2 = map[tmp.x][tmp.y-1];
			if(tmp2.y < now.y+1 && tmp2.x>0) { //또한 왼쪽에 회로가 존재해야 하며, 전기신호가 지금 큐에서 꺼낸 것에 1을 감소한 것보다 더 약하면 탐색을 한다.
				q[qRight].x = tmp.x;
				q[qRight++].y = tmp.y-1; 
				map[tmp.x][tmp.y-1].y = now.y-1;
			}
		}
		}
	}
	
	int ans = 1;
	for(int i=0; i<lampCnt; i++) { //만약 하나라도 lamp의 전기신호가 없다면 실패한 것이다.
		if(map[lamp[i].x][lamp[i].y].y < 1) {
			ans = 0;
			break;
		}
	}
	printf("%s", (char*[]){"failed","success"}[ans]);
}

 

풀이 : DFS

 

0. 변수들을 입력받습니다.

1. BFS을 위한 큐, 좌표에 따른 레드스톤의 정보를 기억할 map, lamp을 저장할 배열을 준비합니다.

2. 회로 정보를 입력 받습니다. 그리고 map을 수정합니다. 여기서 레드스톤 블록은 큐에 저장, 레드스톤 램프는 따로 배열에 저장합니다.

3. BFS을 돌립니다. 상하좌우를 판단합니다.

 여기서 중요한 것은 큐에서 꺼낸 것이 램프이거나 전기신호가 1이라면 더 깊은 탐색을 하지 않으며,

 또한 탐색할 곳의 전기신호가 지금의 전기신호에서 -1 한 것보다 같거나 크다면 이때도 더 깊은 탐색을 하지 않습니다.

4. 2.에서 저장했던 램프들의 좌표를 이용해 모든 램프들의 전기신호가 1이상인지를 판단합니다. 만약 전부다 1 이상이면 success을 그렇지 않다면 failed을 출력합니다.

 

 

기타 : 마인크래프트를 해보면 더욱 쉽게 풀 수 있습니다.

 

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

28291번: 레드스톤