(c++)백준 19237번: 어른 상어

www.acmicpc.net/problem/19237

19237번: 어른 상어

[풀이]

2020상반기 인턴 sw역량평가에 나왔던 문제. 당시에는 자료구조를 잘못 써서 계속 틀렸다.

문제에 주어진대로 시뮬레이션 하면 된다.

다음의 순서로 구현하였다.

1. 모든 상어가 자신의 위치에 냄새를 뿌린다.

2. 1초마다 모든 상어가 조건대로 이동(방향 우선순위 따라 먼저 빈 칸 찾고, 없으면 우선순위 따라 자신의 냄새가 있는 곳 찾기)

3. 겹치는 상어들 중 가장 작은 번호의 상어만 남고 나머지는 격자에서 제외

4. 냄새 갱신(원래 있던 냄새의 제한시간--, 상어가 있는 격자에 새로 냄새 뿌리기)

※Shark구조체에 vector<int>prior[4]를 넣어놓고 입력할 때 각각 Shark객체에 직접 입력해주기! 벡터 배열 만들어서 대입하려고 하면 포인터가 잘못 가리키게 된다.

#include <iostream>
#include <vector>
#include <algorithm>//sort
#include <cstring>//memset
using namespace std;

struct Shark {
	int x, y;
	int d;
	bool live;
	vector<int>prior[4];//방향 우선순위 이대로 포문 돌리기
};

struct Smell {
	int shark;
	int t;
};

int N, M, k;//격자 크기, 상어 수, 냄새 사라지는 시간
int Map[20][20];
Shark shark[401];
Smell smell[20][20];//각 격자 안 냄새 상태
const int dx[] = { 0,-1,1,0,0 };//위, 아래
const int dy[] = { 0,0,0,-1,1 };//왼, 오

void sharkMove() {
	for (int s = 1; s <= M; s++) {
		//쫓겨난 상어면
		if (shark[s].live == false)
			continue;
		int x = shark[s].x;
		int y = shark[s].y;
		int d = shark[s].d;//인덱스 1~4
		bool flag = false;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[shark[s].prior[d-1][i]];
			int ny = y + dy[shark[s].prior[d - 1][i]];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			if (smell[nx][ny].t == 0) {
				flag = true;
				//이동
				shark[s].x = nx;
				shark[s].y = ny;
				shark[s].d = shark[s].prior[d - 1][i];
				break;
			}
		}
		//빈 칸이 없는 경우
		if (flag == false) {
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[shark[s].prior[d - 1][i]];
				int ny = y + dy[shark[s].prior[d - 1][i]];
				if (nx < 0 || nx >= N || ny < 0 || ny >= N)
					continue;
				if (smell[nx][ny].shark == s) {
					//이동
					shark[s].x = nx;
					shark[s].y = ny;
					shark[s].d = shark[s].prior[d - 1][i];
					break;
				}
			}
		}
	}
}

void updateSmell() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			//냄새가 남아있으면
			if (smell[i][j].t > 0) {
				smell[i][j].t--;
			}
			//상어가 있는 자리면
			if (Map[i][j] > 0) {
				smell[i][j].shark = Map[i][j];
				smell[i][j].t = k;
			}
		}
	}
}


void removeShark() {
	memset(Map, 0, sizeof(Map));
	for (int i = 1; i <= M; i++) {
		if (shark[i].live == false)
			continue;
		int x = shark[i].x;
		int y = shark[i].y;
		if (Map[x][y] == 0)
			Map[x][y] = i;
		else {
			if (Map[x][y] < i)
				shark[i].live = false;
			else {
				shark[Map[x][y]].live = false;
				Map[x][y] = i;
			}
		}
	}
}

//끝나는 조건: 1번 상어만 남았는지 확인
bool End() {
	for (int i = 2; i <= M; i++) {
		if (shark[i].live == true)
			return false;
	}
	return true;
}

void solution() {
	cin >> N >> M >> k;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
			//상어가 있으면
			if (Map[i][j] != 0) {
				shark[Map[i][j]] = { i,j,-1,true };//방향, 우선순위 제외 미리 저장
				smell[i][j] = { Map[i][j],k };//냄새 뿌린 상태로 시작
			}
			else
				smell[i][j] = { 0,0 };
		}
	}
	//각 상어 방향 저장
	for (int i = 1; i <= M; i++) {
		int d;
		cin >> d;
		shark[i].d = d;
	}
	//우선순위 저장
	for (int i = 1; i <= M; i++) {
		for (int x = 0; x < 4; x++) {
			for (int y = 0; y < 4; y++) {
				int a;
				cin >> a;
				shark[i].prior[x].push_back(a);
			}
		}
	}
	//상어1만 남을 때까지
	int t = 0;
	while (!End()) {
		sharkMove();
		removeShark();
		updateSmell();
		t++;
		if (t > 1000) {
			t = -1;
			break;
		}
	}
	cout << t << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	solution();
	return 0;
}

+ 방향에 따른 우선순위를 배열에 따로 저장하는 방법

#include <iostream>
#include <cstring>//memset
using namespace std;

struct Smell {
	int n;//냄새 주인
	int cnt;//냄새 기한 얼마나 남았는지
};

struct Shark {
	int x, y;
	int d;//상어 방향
	bool dead;
};

int N, M, k;
Smell smell[20][20];
Shark shark[401];
int Map[20][20];
const int dxy[][2] = { {0,0},{-1,0},{1,0},{0,-1},{0,1} };
int prior[401][5][5];//각 상어의 방향에 따른 우선순위

bool checkFinish() {
	for (int i = 2; i <= M; i++) {
		if (shark[i].dead == false)
			return false;
	}
	return true;
}

void moveShark() {
	//1번 상어부터 차례대로 움직이기
	for (int i = 1; i <= M; i++) {
		//쫓겨난 상어면 건너뛰기
		if (shark[i].dead == true)
			continue;
		int x = shark[i].x;
		int y = shark[i].y;
		int d = shark[i].d;
		int nx;
		int ny;
		int nd;
		bool moved = false;
		for (int p = 1; p <= 4; p++) {
			nd = prior[i][d][p];
			nx = x + dxy[nd][0];
			ny = y + dxy[nd][1];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			//아무 냄새도 없는 칸 발견하면
			if (smell[nx][ny].n == 0) {
				moved = true;
				shark[i].x = nx;
				shark[i].y = ny;
				shark[i].d = nd;
				break;
			}
		}
		//아무 냄새 없는 칸이 없으면
		if (moved == false) {
			for (int p = 1; p <= 4; p++) {
				nd = prior[i][d][p];
				nx = x + dxy[nd][0];
				ny = y + dxy[nd][1];
				if (nx < 0 || nx >= N || ny < 0 || ny >= N)
					continue;
				//같은 냄새 칸 발견하면
				if (smell[nx][ny].n == i) {
					moved = true;
					shark[i].x = nx;
					shark[i].y = ny;
					shark[i].d = nd;
					break;
				}
			}
		}
	}
	//잡아먹기
	memset(Map, 0, sizeof(Map));
	for (int i = 1; i <= M; i++) {
		if (shark[i].dead == true)
			continue;
		int x = shark[i].x;
		int y = shark[i].y;
		if (Map[x][y] == 0)
			Map[x][y] = i;
		else {
			if (Map[x][y] < i)
				shark[i].dead = true;
			else {
				shark[Map[x][y]].dead = true;
				Map[x][y] = i;
			}
		}
	}
}

void countSmell() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			//상어가 있으면
			if (Map[i][j] > 0) {
				smell[i][j].n = Map[i][j];
				smell[i][j].cnt = k;
			}
			else if (smell[i][j].cnt > 0) {
				smell[i][j].cnt--;
			}
			if (smell[i][j].cnt == 0)
				smell[i][j].n = 0;
		}
	}
}

int main() {
	cin >> N >> M >> k;
	int num;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> num;
			Map[i][j] = num;
			if (num == 0)
				smell[i][j] = { 0,0 };
			else {
				shark[num] = { i,j,0,false };
				//냄새 뿌림
				smell[i][j] = { num,k };
			}
		}
	}
	int d;
	//각 상어의 처음 방향
	for (int i = 1; i <= M; i++) {
		cin >> shark[i].d;
	}
	//각 상어의 방향에 따른 우선순위
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 1; k <= 4; k++) {
				cin >> prior[i][j][k];
			}
		}
	}
	int t = 0;
	while (1) {
		if (t > 1000) {
			t = -1;
			break;
		}
		if (checkFinish())
			break;
		moveShark();
		countSmell();
		t++;
	}
	cout << t << '\n';
	return 0;
}