백준 19237 : 어른 상어

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

19237번: 어른 상어

 

풀기 싫게 생겨서 미루고 미루다 이제야 푼 문제.

단순 깡 구현인데 깔끔하게 짜고싶었지만 별로 그렇지 않은 것 같다.

 

문제 해결 논리는 다음과 같다.

 

0. 상어는 어차피 한 턴에 한 방향으로만 움직이므로 상어 정보를 구조체 배열로 관리하고 상어 번호만 큐에 넣어 이동할 상어와 격자 밖으로 쫓겨난 상어를 구분한다.

1. 판 위에 이미 뿌려진 체취가 옅어지고 상어가 현재 위치에 체취를 뿌리고 다음 칸으로 이동하는 것을 한 턴으로 본다.

2. 턴이 시작되는 시점에 모든 상어가 체취를 다 뿌리고 나서 상어를 하나씩 이동시킨다.

   상어를 한 마리 씩 체취 뿌리고 이동하고 하는 식으로 할 시 상어의 순서에 따라 상어의 이동 방향이 달라질 수 있다

 

코드로 구현하면 아래와 같다.

#include <iostream>
#include <queue>

#define SHARK first
#define SMELL second

struct SharkInfo {
	int x, y, dir;
};

using namespace std;
using pii = pair<int, int>;

int n, m, k;
pii board[21][21];

int dir[401][5][4];
int dxdy[5][2] = { {0, 0}, {0, -1}, {0, 1}, {-1, 0}, {1, 0} };

queue<int> q;
SharkInfo sharks[401];

void input() {
	int tmp;

	//상어 정보 갱신 및 큐에 상어 번호 추가
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tmp;
			if (tmp)
				sharks[tmp] = { j, i, 0 };
		}
	}

	for (int i = 1; i <= m; i++) {
		cin >> sharks[i].dir;
		q.emplace(i);
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> dir[i][j][k];
			}
		}
	}
}

int bfs() {
	SharkInfo* cur;
	int nx, ny, ndir, cur_num;
	int remain = 0, turn = -1;

	while (!q.empty() && turn <= 1000) {
		//턴 시작 시
		if (remain <= 0) {
			++turn; remain = q.size();
			//체취 감소 및 제거
			for (int y = 0; y < n; y++) {
				for (int x = 0; x < n; x++) {
					if (board[y][x].SMELL) {
						--board[y][x].SMELL;
						if (!board[y][x].SMELL)
							board[y][x].SHARK = 0;
					}
				}
			}

			//모든 상어가 체취를 뿌림
			for (int i = 0; i < remain; i++) {
				cur_num = q.front();
				cur = &sharks[cur_num];
				q.pop();

				//다른 상어에게 잡아먹힌 경우
				//체취가 없거나 본인 체취인 곳에만 이동이 가능하므로
				//현재 위치에 다른 상어의 체취가 있다는 것은 본인보다 더 빠른 번호의
				//상어가 이번 턴에 체취를 뿌렸다는 것, 따라서 해당 상어는 큐에 넣지 않는다.
				if (board[cur->y][cur->x].SHARK &&
					board[cur->y][cur->x].SHARK != cur_num) {
					continue;
				}

				board[cur->y][cur->x].SHARK = cur_num;
				board[cur->y][cur->x].SMELL = k;

				q.emplace(cur_num);
			}

			//만약 상어가 한 마리만 남았다면 종결
			if (q.size() <= 1) break;
			//큐에 들어있는 원소들을 한번씩 싹 다 꺼내서 처리하면 한 턴이 지난걸로 한다.
			//턴을 체크하기 위해 큐에 들어있는 원소의 개수를 저장한다.
			remain = q.size();
		}
		
		//상어 이동
		cur_num = q.front();
		cur = &sharks[cur_num];
		q.pop();

		for (int i = 0; i < 5; i++) {
			//0~3 까지는 주변에 빈 곳 탐색
			if (i < 4) {
				ndir = dir[cur_num][cur->dir][i];
				nx = cur->x + dxdy[ndir][0];
				ny = cur->y + dxdy[ndir][1];

				if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
				if (board[ny][nx].SHARK) continue;

				break;
			}
			//4까지 올 시 주변에 빈 곳이 없는 것이므로
			//자신의 체취가 있는 곳 중 우선순위가 높은 곳으로 이동
			else {
				for (int i = 0; i < 4; i++) {
					ndir = dir[cur_num][cur->dir][i];
					nx = cur->x + dxdy[ndir][0];
					ny = cur->y + dxdy[ndir][1];

					if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
					if (board[ny][nx].SHARK != cur_num) continue;

					break;
				}
			}
		}

		//상어 정보 배열 갱신
		cur->x = nx, cur->y = ny, cur->dir = ndir;
		q.emplace(cur_num);

		--remain;
	}

	return turn > 1000 ? -1 : turn;
}

void solution() {
	input();
	cout << bfs();
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2064 kb

시간: 0 ms