[Algorithm][BFS][정올] 1078 : 저글링 방사능 오염

I. 문제

승훈이는 심심한 시간에 스타크래프트(Starcraft) 게임을 하며 놀고 있었다.
스타크래프트 유닛 중 하나인 저글링을 한 곳에 몰아세운 뒤, 방사능 오염 공격으로 없애보려고 했다. 
그런데 좀 더 재미있게 게임을 하기 위해서 게임을 개조하여 방사능 오염 공격을 가하면 방사능은 1초마다 이웃한 저글링에 오염된다. 
그리고 방사능에 오염된 저글링은 3초 후에 죽게 된다. 
예를 들어 아래 왼쪽그림과 같이 모여 있는 저글링 중에 빨간 동그라미 표시를 한 저글링에게 방사능 오염 공격을 가하면, 
총 9초 후에 저글링들이 죽게 된다. 아래 오른쪽에 있는 그림의 숫자들은 각 저글링들이 죽는 시간이다.

저글링을 모아놓은 지도의 크기와 지도상에 저글링들이 놓여 있는 격자 위치가 주어질 때,
총 몇 초 만에 저글링들을 모두 없앨 수 있는지 알아보는 프로그램을 작성하시오.

>> 요약 : 주어진 위치부터 1초마다 상하좌우로 저글링이 오염되고 오염되면 3초뒤에 죽는다.
             다 죽는데 몇 초? 남은 마리수는?

입력 형식 첫째 줄은 지도의 열, 행 (지도는 격자구조) 크기는 최대 100x100 둘째 줄부터 저글링 놓여있는 상황 (1 : 저글링O, 0 : 저글링X) 마지막 줄에는 방사능오염을 가하는 위치가 열 번호 행 번호 순으로 주어짐	출력 형식 죽을 수 있는 저글링이 모두 죽을 때 까지 몇초가 걸리는지 첫 줄에 출력, 둘째 줄에 죽지 않고 남아 있게 되는 저글링의 수 출력
7 8  0010000  0011000  0001100  1011111  1111011  0011100  0011100  0001000 3 5	9 0

 

---

II. 접근 (BFS)

미로 찾기와 다른 점은, 시작 위치가 변경되고 끝 위치는 지정되어있지 않다.

<시간 구하기>
1. 확산해야 하는 맵의 위치 정보를 구조체로 담는다 struct(y, x, t) 

2. 시작 위치부터 시작하여 동서남북 탐색해 저글링이 있다면 (map[y][x] == 1) 
    그 위치 정보를 담은 구조체를 Queue. push(struct {nexty, nextx, nextt})

3. 다음 위치로 이동(cur = Queue.front(), Queue.pop())후에 cur위치에 대해 2. 반복

* 끝 위치가 지정되어 있지 않으므로 Queue. empty()==True 상태일 때까지 반복한다. -> 모두 확산 끝
* 3초 뒤 죽는 상황은 신경 쓰지 말고 그냥 답에 +3 혹은 처음에 +3

<남은 마릿수 구하기>
1. 처음 input 단계에서 변수에 저글링이 총 몇 마리인지 저장.

2. 저글링 맵에 방문할 때(Queue. push())마다 변수-- 해줌.

 

---

III. 코드

<hide/>
#include <stdio.h>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct stu {
	int y;
	int x;
	int t;
};

int col, row;

int map[100 + 10][100 + 10]; // 훼손하며 방문표시할 것임.
int remain{ 0 }; //남은 저글링 수


queue <stu> Q;

void input() {
    memset(map, 0, sizeof(map));
	cin >> row >> col;
	for (int i = 1; i <= col; i++) {
		for (int j = 1; j <= row; j++) {
			scanf("%1d", &map[i][j]);
			if (map[i][j]) remain++; //1이면 저글링 수 ++
		}
	}

	int sx;
	int sy;
	cin >> sx >> sy;
	Q.push(stu{ sy,sx,0 }); // 처음 위치정보 입력
	map[sy][sx] = 0; // 방문표시
	remain--; //첫 위치 저글링 죽음
}

int BFS() {
	int dx[4] = { -1,0,0,1 };
	int dy[4] = { 0,1,-1,0 };
	int tottime{ 0 };

	while (!Q.empty()) {
		stu curstu = Q.front();
		tottime = curstu.t; //얼마나 걸리는지 변수 입력.
		Q.pop();
		for (int i = 0; i < 4; i++) {
			// 다음 위치정보 업데이트
			int nexty = curstu.y + dy[i];
			int nextx = curstu.x + dx[i];
			int nextt = curstu.t + 1;

			if (nexty == 0 or nextx == 0 or
				nexty == col + 1 or nextx == row + 1) continue;

			if (map[nexty][nextx]) {
				Q.push(stu{ nexty,nextx,nextt }); // Q에 push
				map[nexty][nextx] = 0; //방문 체크
				remain--; // 저글링 제거
			}
		}
	}
	return tottime;
}

int main() {

	input();

	int timeans = BFS();

	cout << timeans+3 << endl << remain; //+3 : 3초 뒤 반영
}

 

문제 출처 jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358&sca=3040