[백준] 어른상어

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

19237번: 어른 상어

 

마지막에 answer >= 1000 조건에서 = 조건 안넣어서 틀림.... 

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int answer;
int N, M, k;

struct Shark {
	int row;
	int col;
	int num;
	int dir;
};

vector< vector<int> > board[21][21]; //{num, 냄새}
vector<Shark> sharkes;
vector<int> priorities[5][401]; //row: 방향, col : 상어번호

int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,-1,1 };

void init() {
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < 21; j++) {
			board[i][j] = {};
		}
	}

	sharkes = {};

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 401; j++) {
			priorities[i][j] = {};
		}
	}
}

bool comp(Shark s1, Shark s2) {
	return s1.num < s2.num;
}

bool comp2(vector<int> v1, vector<int> v2) {
	if (v1[0] == v2[0]) {
		return v1[1] > v2[1];
	}
	else {
		return v1[0] < v2[0];
	}
}

void input() {
	cin >> N >> M >> k;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int num;
			cin >> num;
			if (num > 0) { //상어
				board[i][j] = {{num, k}};
				sharkes.push_back({ i,j,num,0 });
			}
		}
	}

	sort(sharkes.begin(), sharkes.end(), comp);
	
	for (int i = 0; i < M; i++) {
		int d;
		cin >> d;
		sharkes[i].dir = d;
	}

	//우선순위
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= 4; j++) {
			int p;
			vector<int> temp;
			for (int k = 0; k < 4; k++) {
				cin >> p;
				temp.push_back(p);
			}
			priorities[j][i] = temp;
		}
	}
}

void print() {

	cout << "상어 위치" << endl;
	for (int i = 0; i < sharkes.size(); i++) {
		cout << i << " : " << sharkes[i].row << " " << sharkes[i].col << " " << sharkes[i].num << " " << sharkes[i].dir << endl;
	}
	cout << endl;

	cout << "냄새" << endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < board[i][j].size(); k++) {
				cout << i << " " << j << " : " << board[i][j][k][0] << " " << board[i][j][k][1] << endl;
			}
		}
	}

	cout << endl;
	cout << " ----------------------- " << endl;
}

bool inRange(int r, int c) {
	return r >= 0 && r < N&& c >= 0 && c < N;
}

int decideDir(int row, int col, int num, int dir) {
	vector< vector<int> > candidate1; // 냄새없는 경우
	vector< vector<int> > candidate2; // 자신의 냄새가 있는 경우

	// 후보 찾기.
	for (int i = 1; i <= 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];

		if (inRange(nr, nc)) {
			if (board[nr][nc].size() == 0) {
				candidate1.push_back({ nr,nc,i });
			}
			else {
				for (int j = 0; j < board[nr][nc].size(); j++) {
					if (board[nr][nc][j][0] == num) {
						candidate2.push_back({ nr,nc,i });
					}
				}
			}
		}
	}

	if (candidate1.size() > 0) { //냄새가 없는 칸이 있는 경우.
		for (int p = 0; p < 4; p++) { //priorities[d][n]
			int nd = priorities[dir][num][p];
			for (int i = 0; i < candidate1.size(); i++) {
				if (candidate1[i][2] == nd) {
					return nd;
				}
			}
		}
	}
	else if (candidate2.size() > 0){ //자신의 냄새가 있는 경우
		for (int p = 0; p < 4; p++) { //priorities[d][n]
			int nd = priorities[dir][num][p];
			for (int i = 0; i < candidate2.size(); i++) {
				if (candidate2[i][2] == nd) {
					return nd;
				}
			}
		}
	}
	else {
		for (int p = 0; p < 4; p++) { //priorities[d][n]
			int nd = priorities[dir][num][p];
			int nr = row + dr[nd];
			int nc = col + dc[nd];
			if (inRange(nr, nc)) {
				return nd;
			}
		}
	}
}

void moveShark(vector<vector<int>> &s) {
	
	for (int i = 0; i < s.size(); i++) {
		int idx = s[i][0];
		int row = s[i][1];
		int col = s[i][2];
		int num = s[i][3];
		int nd = s[i][4];

		int nr = row + dr[nd];
		int nc = col + dc[nd];

		//상어 이동
		sharkes[idx] = { nr,nc,num,nd };

		//이동한 위치 냄새 추가
		board[nr][nc].push_back({ num, k });
	}
}

void deleteShark() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (board[r][c].size() > 1) {
				sort(board[r][c].begin(), board[r][c].end(), comp2);

				int target = board[r][c][0][0];
				vector<int> temp = board[r][c][0];
				board[r][c].clear();
				board[r][c].push_back(temp);

				vector<Shark>::iterator iter;
				for (iter = sharkes.begin(); iter != sharkes.end();) {
					Shark s = *iter;
					if (s.row == r && s.col == c && s.num != target) {
						iter = sharkes.erase(iter);
					}
					else {
						iter++;
					}
				}
			}
		}
	}
}

bool check() {
	if (sharkes.size() == 1) {
		return false;
	}

	for (int i = 0; i < sharkes.size(); i++) {
		if (sharkes[i].num == 1) {
			return true;
		}
	}
	return false;
}

void solve() {

	while (check()) {
		if (answer >= 1000) {
			answer = -1;
			return;
		}

		//냄새 줄이기.
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if (board[r][c].size() > 0) {
					vector<int> v = board[r][c][0];
					if (v[1] > 0) {
						board[r][c][0][1]--;
					}
					else if (v[1] == 0) {
						board[r][c] = {};
					}
				}
			}
		}

		//이동할 상어 저장
		vector<vector<int>> temp_shark;

		for (int i = 0; i < sharkes.size(); i++) {
			int r = sharkes[i].row;
			int c = sharkes[i].col;
			int n = sharkes[i].num;
			int d = sharkes[i].dir;

			//이동방향 결정
			int nd = decideDir(r, c, n, d);

			//상어 이동
			temp_shark.push_back({ i,r,c,n,nd });
		}
		moveShark(temp_shark);

		//한 칸에 여러마리의 상어가 남아있으면 제거.
		deleteShark();

		//print();
		answer++;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);

	//init();
	input();
	solve();

	cout << answer << endl;
	return 0;
}