백준 19237번 어른 상어

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

19237번: 어른 상어

겉보기에는 복잡해보이지만 다차원 배열을 활용하면 생각보다 간단한 문제였습니다.

알고리즘은 아래와 같습니다.

1. 입력을 모두 받고 각 상어의 방향마다의 우선순위를 입력받기 위해 삼차원 배열을 다음과 같이 선언해줍니다. [상어 번호][현재 방향][현재 방향에 따른 우선순위 방향]

2. 이동을 하는데 상어가 동시에 이동하므로 냄새와 이동한 상어의 좌표를 바로 적용해주지 않고 별도의 Scent 자료형의 v 벡터에 이동한 정보를 저장해줍니다.

2.1 이 때 상어가 이동은 했으므로 기존에 상어가 있던 곳은 비어있다고 표시해주고 sharkDirection 배열에 상어가 이동한 방향을 표시해줍니다.

3. 2번에서 상어가 이동했으므로 상어의 냄새 지속시간을 하나씩 감소해줍니다.

3.1 이 때, 상어의 지속시간이 0 미만으로 가지 않도록 적절히 처리해줍니다.

4. 문제 조건에서 상어들이 동시다발적으로 움직였을 때 같은 칸에 겹치면 상어 번호가 제일 작은 상어만 산다고 명시했기 때문에 v 벡터를 상어 번호 오름차순으로 정렬을 해줍니다.

5. 정렬된 v 벡터를 순회하며 비어있는 sharkTank 배열에 상어들을 하나씩 배치해주고 냄새도 기록해줍니다.

5.1 배치한 칸에 다른 상어가 위치하려고 한다면 이미 탈출한 상어라는 뜻이므로 M을 1 감소시키고 배치해주지 않습니다.

6. 반복문을 1000번 돌리기 전에 M이 1이 된다면 가장 작은 번호인 1번 상어만 살아남았다는 뜻이므로 시간을 출력해줍니다.

6.1 반복문을 1000번 돌렸는데도 불구하고 M이 1이 아니라면 -1을 출력해주고 프로그램을 종료해줍니다.

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	const int MAX = 20;
	const int SCENT_MAX = 1000;
	typedef struct
	{
	int y, x;
	}Dir;
	Dir moveDir[5] = { {0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
	typedef struct
	{
	int sharkIdx, time;
	}Scent;
	typedef struct
	{
	int y, x;
	int sharkIdx, time;
	}State;
	bool cmp(State a, State b)
	{
	return a.sharkIdx < b.sharkIdx;
	}
	int N, M, K;
	int sharkTank[MAX][MAX];
	Scent sharkScent[MAX][MAX];
	int sharkDirection[MAX * MAX + 1];
	int movePriority[MAX * MAX + 1][5][4];
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < N; j++)
	{
	int sharkIdx;
	cin >> sharkIdx;
	if (sharkIdx == 0)
	{
	continue;
	}
	sharkTank[i][j] = sharkIdx;
	sharkScent[i][j] = { sharkIdx, K };
	}
	}
	for (int i = 1; i <= M; i++)
	{
	cin >> sharkDirection[i];
	}
	for (int i = 1; i <= M; i++)
	{
	for (int j = 1; j <= 4; j++)
	{
	for (int k = 0; k < 4; k++)
	{
	int move;
	cin >> move;
	movePriority[i][j][k] = move;
	}
	}
	}
	for (int t = 1; t <= 1000; t++)
	{
	vector<State> v;
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < N; j++)
	{
	if (sharkTank[i][j] == 0)
	{
	continue;
	}
	// 상어 이동
	bool flag = false;
	int sharkIdx = sharkTank[i][j];
	int dir = sharkDirection[sharkIdx];
	// 이동하므로
	sharkTank[i][j] = 0;
	// 냄새가 없는 칸으로 이동
	for (int k = 0; k < 4; k++)
	{
	int move = movePriority[sharkIdx][dir][k];
	int nextY = i + moveDir[move].y;
	int nextX = j + moveDir[move].x;
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N)
	{
	continue;
	}
	if (sharkScent[nextY][nextX].time)
	{
	continue;
	}
	flag = true;
	v.push_back({ nextY, nextX, sharkIdx, K });
	sharkDirection[sharkIdx] = move;
	break;
	}
	if (flag)
	{
	continue;
	}
	// 자신의 냄새가 있는 곳으로 이동
	for (int k = 0; k < 4; k++)
	{
	int move = movePriority[sharkIdx][dir][k];
	int nextY = i + moveDir[move].y;
	int nextX = j + moveDir[move].x;
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N)
	{
	continue;
	}
	if (sharkScent[nextY][nextX].sharkIdx != sharkIdx)
	{
	continue;
	}
	v.push_back({ nextY, nextX, sharkIdx, K });
	sharkDirection[sharkIdx] = move;
	break;
	}
	}
	}
	// 냄새 제거
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < N; j++)
	{
	if (sharkScent[i][j].time == 0)
	{
	continue;
	}
	int sharkIdx = sharkScent[i][j].sharkIdx;
	sharkScent[i][j].time--;
	}
	}
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < v.size(); i++)
	{
	int y = v[i].y;
	int x = v[i].x;
	int sharkIdx = v[i].sharkIdx;
	if (sharkTank[y][x])
	{
	M--;
	continue;
	}
	sharkTank[y][x] = sharkIdx;
	sharkScent[y][x] = { sharkIdx, K };
	}
	if (M == 1)
	{
	cout << t << "\n";
	return 0;
	}
	}
	cout << -1 << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2019

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~