18405 경쟁적 전염

BFS Flood Fill 문제

동시에 여러 세균들을 퍼트리고

특정 시간에서 맵 상태를 확인한다

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

1. 문제

---

간단 설명

N*N에 K개의 세균이 주어짐

각 세균은 1초마다 상하좌우로 퍼짐

다른 세균이 있으면 더이상 퍼지지 못함

S초가 됬을 때, y, x 좌표에 어떤 세균이 있는지 찾는 문제

2. 문제 분석

---

필요변수

맵 사이즈 N, 세균 개수 K

맵 정보 map[MAX][MAX], 방문 여부 visited[MAX][MAX]

좌표 구조체 struct Node{int y; int x; int num, int time}

y, x 좌표와 어떤 세균인지(num) 몇초에 퍼졌는지(time) 정보를 가짐

4방향 direct[4][2]

주의점

• 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식함. 낮은 순서대로 큐에 넣어줘야한다

• 언제 초를 갱신할 것인지 주의해야한다

알고리즘

1. N, K 와 맵 정보 입력받기
2. S와 목표 좌표 입력받기
3. BFS 돌리기
    3-1. 큐 생성 및 낮은 번호 순서대로 세균의 좌표를 큐에 넣고 방문처리
    - 최대 1000 * 201 * 201 = 40,000,000. 10억이 대략 1초니까 시간 복잡도 OK
    - 큐에 넣을 때 {(y, x), 세균번호, 0초} 로 저장한다
    3-2. 큐에서 맨 앞을 꺼내 Now에 저장
    3-3. now의 초가 목표 시간 S랑 같다면 종료
    3-4. now에서 4방향으로 탐색한다
        - 경계 밖이라면 패스
        - 이미 다른 세균이 있다며 ㄴ패스
        - 이미 방문한 곳이라면 패스
    3-5. 위 조건들을 통과했다면, 방문 처리후 현재 세균 번호를 기록한다
    3-6. 큐에 {dy, dx, 세균번호, 시간 + 1초}를 넣는다 
4. BFS가 종료되면 타겟 좌표에 있는 세균을 출력한다

3. 소스코드

---

#include <iostream>
#include <queue>

using namespace std;

#define MAX 201

int N, K, S;
int map[MAX][MAX];
int visited[MAX][MAX];

struct Node{
	int y;
	int x;
	int num;
	int time;
};
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };

// 세균의 번호를 입력받아 그 세균을 증식시키는 BFS
void BFS() {
	queue<Node> qu;

	// 1번 바이러스부터 K번까지 차례로 큐에 넣음
	for (int i = 1; i <= K; i++) { 
        // 최대 1000 * 201 * 201 = 40,000,000. 10억이 대략 1초니까 시간 복잡도 OK
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (map[y][x] == i) {
					qu.push({ y, x, i, 0 }); // 0초로 지정
					visited[y][x] = 1; // 방문처리 
				}
			}
		}
	}

	// S초 까지 BFS를 돌린다 
	int sec = 0;
	while (!qu.empty()) {
		Node now = qu.front();
		qu.pop();

		if (now.time == S) break;

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;

			if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue; // 경계 처리
			if (map[dy][dx] != 0) continue; // 다른 세균
			if (visited[dy][dx] == 1) continue; // 이미 방문

			visited[dy][dx] = 1;
			map[dy][dx] = now.num;
			qu.push({ dy, dx, now.num, now.time + 1 });
		}
	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
    // 1. 맵 정보 입력
	cin >> N >> K;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
		}
	}
    // 2. 시간 및 타겟 입력
	int target_y, target_x;
	cin >> S >> target_y >> target_x;

    // 3. BFS
	BFS();

    // 4. 출력
	cout << map[target_y-1][target_x-1];

	return 0;
}