백준 18045 - 경쟁적 전염(C++)

문제 링크입니다. https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

BFS 이용해 푸는 문제입니다.

 

 

1번 바이러스부터 K번 바이러스까지 순차적으로 4방향으로 퍼트리는 문제입니다.

순차적으로 퍼지기에, 큐에 1번부터 K번까지 차례대로 넣어준뒤 BFS 탐색을 해야합니다.

 

코드에서 정렬을 한 이유는 1번부터 K번까지 순서대로 큐에 넣고 시작하기 위해 정렬을 해줬습니다.

 

탐색을 하는 중에서 큐에 새로운 데이터를 넣는 조건입니다.

1. (X,Y) 좌표를 탐색하려고 할때, 탐색 범위가 Map의 범위를 넘지 않는다.

2. check 배열에 이미 값이 있으면 탐색하지 않는다. -> 이미 다른 바이러스에 감염됐다는 의미

3. 찾길 윈하는 시간 이내에 탐색을 해야한다.

 

탐색을 전부 마친 뒤에는 찾길 윈하는 좌표에서의 check 배열의 값을 출력하면 됩니다.

바이러스가 퍼져있다면 해당 바이러스의 번호가 나올 것이며, 퍼지지 않았다면 0의 값이 출력되기 때문입니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

int Map[201][201];
int check[201][201];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int N, K;
int Time, fin_x, fin_y;
vector<pair<int, pair<int, int>>> virus;

bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
	if (a.first < b.first) return true;
	else return false;
}

void bfs() {
	queue<pair<pair<int,int>, pair<int, int>>> q;
	for (int i = 0; i < virus.size(); i++) {
		q.push({ {virus[i].first, 0}, {virus[i].second} });
		check[virus[i].second.first][virus[i].second.second] = virus[i].first;
	}
	while (!q.empty()) {
		int x = q.front().second.first;
		int y = q.front().second.second;
		int num = q.front().first.first;
		int cnt = q.front().first.second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
				if (check[xx][yy] == 0 && cnt + 1 <= Time) {
					check[xx][yy] = num;
					q.push({ {num,cnt + 1},{xx,yy} });
				}
			}
		}
	}
}

void solve() {
	sort(virus.begin(), virus.end(), cmp);
	bfs();
	cout << check[fin_x][fin_y];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> Map[i][j];
			if (Map[i][j] > 0) virus.push_back({ Map[i][j], {i,j} });
		}
	}
	cin >> Time >> fin_x >> fin_y;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!