백준 6166(Meteor Shower)

www.acmicpc.net/problem/6166

6166번: Meteor Shower

구현 문제.. 

 

그냥 bfs이다. 딱 봐도 그렇다 

왜냐 턴제 문제이기 때문에, 메테오가 충돌하고, 원래 남아있던 bessie 중에 죽은 애들은 다 처리하고 

남아 있는애들은 인접한 파괴되지 않은 곳으로 이동한다. 

 

남아 있는 애들 중에서 최단 시간 동안 이동했을때 살아남은 애들을 구하는 문제.

 

그냥 구현을 잘 하자 bfs 이고, 시간을 vector[] 로 저장하는게 중요한 듯하다.

 

그리고 queue 두개 쓸때는 항상 조심하도록 하자 while문을 두개 연속으로 쓰다가 디버깅하는데 엄청 힘들었다.

 

#include<iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
#define MAX 305

bool attack[MAX][MAX];
bool check[MAX][MAX];
int M, last;
queue<pair<int, pair<int, int> > > q;
queue<pair<int, pair<int, int> > > q2;

vector<pair<int, int> > v[1005];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void bfs() {
	for (int i = 0; i <= last; i++) {
		for (int j = 0; j < v[i].size(); j++) {
			pair<int, int> p = v[i][j];
			attack[p.first][p.second] = true;
			for (int m = 0; m < 4; m++) {
				int x = p.first + dx[m];
				int y = p.second + dy[m];
				if (x >= MAX || y >= MAX || x < 0 || y < 0) continue;
				attack[x][y] = true;
			}
		}
		if (!q.empty()) {
			while (!q.empty()) {
				int a = q.front().first;
				pair<int, int> p = q.front().second;
				q.pop();
				if (!attack[p.first][p.second]) {
					q2.push(make_pair(a, p));
					for (int m = 0; m < 4; m++) {
						int x = p.first + dx[m];
						int y = p.second + dy[m];
						if (x < 0 || y < 0 || attack[x][y] || check[x][y]) continue;
						q2.push(make_pair(a + 1, make_pair(x, y)));
						check[x][y] = true;
					}
				}
			}
		}
		else {
			while (!q2.empty()) {
				int a = q2.front().first;
				pair<int, int> p = q2.front().second;
				q2.pop();
				if (!attack[p.first][p.second]) {
					q.push(make_pair(a, p));
					for (int m = 0; m < 4; m++) {
						int x = p.first + dx[m];
						int y = p.second + dy[m];
						if (x < 0 || y < 0 || attack[x][y] || check[x][y]) continue;
						q.push(make_pair(a + 1, make_pair(x, y)));
						check[x][y] = true;
					}
				}
			}
		}
	}
}

int main() {
	cin >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (last < c)last = c;
		v[c].push_back(make_pair(a, b));
	}
	q.push(make_pair(0, make_pair(0, 0)));
	check[0][0] = true;
	bfs();

	int ans = 987654321;
	pair<int, int> p;
	while (!q.empty()) {
		int b = q.front().first;
		if (ans > b) {
			ans = b;
			p = q.front().second;
		}
		q.pop();

	}
	while (!q2.empty()) {
		int b = q2.front().first;
		if (ans > b) {
			ans = b;
			p = q2.front().second;

		}
		q2.pop();

	}
	if (ans == 987654321) {
		cout << -1 << '\n';
		return 0;
	}
	cout << ans << "\n";
}