[C++] 백준 19237 어른 상어

문제 링크

---

문제 링크

www.acmicpc.net/problem/19237

19237번: 어른 상어

 

접근 방법

---

이 문제 또한 구현 및 시뮬레이션 문제였습니다. 

구현을 위해 두가지 구조체를 사용하였습니다. 

 

1. 상어의 방향의 우선순위를 정하기 위한 sharkInfo 입니다. 상어의 현재 진행 방향을 dir, dir에 따른 방향의 우선 순위를 지정하기위한 priority[dir][i]입니다.

typedef struct sharkInfo {
	int dir;
	vector<vector<int>> priority;
};

 

2. 또한 격자의 상태를 나타내기 위한 mapInfo 입니다. 어떤 상어의 냄새인지를 나타내는 num, 냄새가 사라지기 까지 남은 시간 time, 상어의 실제 존재 유무 exist입니다.

typedef struct mapInfo {
	int num, time;
	bool exist;
};

 

 

 이제 1초 동안 일어나는 일에 대해서 생각해 봐야 합니다. 저는 이러한 과정을 3가지로 나누어 생각했습니다.

1. 상어들이 이동할 다음 좌표를 알아낸다.

2. 1에서 찾은 좌표들로 상어들을 이동시킨다.(이 때 번호가 작은 상어가 번호가 큰 상어를 내 쫒음)

3. 전체의 격자에서 냄새가 사라지기 까지 남은 시간인 time을 갱신한다.

 

1. 한 상어의 좌표를 받아 상어의 번호와 다음 좌표를 반환하는 함수를 구현하였습니다.

일단 현재 냄새가 없는 곳으로 갈 수 있는지 탐색 후 그러한 공간이 없다면 자신의 냄새가 있던 곳을 탐색하게 됩니다.

이 때 sharks는 sharkInfo의 정보들을 담고 있는 전역의 벡터 입니다.

pair<int, pair<int, int>> findNextCoord(int x, int y) {

	int num = map[x][y].num;
	sharkInfo shark = sharks[num];
	int dir = shark.dir;

	int next_x = x;
	int next_y = y;
	
    //냄새가 없는 곳을 탐색
	for (int i = 0; i < 4; i++) {
		int nextdir = shark.priority[dir][i];
		next_x = x + direction[nextdir].first;
		next_y = y + direction[nextdir].second;
		if (canMove(next_x, next_y)) {
			sharks[num].dir = nextdir;
			break;
		}
	}
    //그러한 공간이 없다면 자신의 냄새가 있던 곳을 탐색
	if (!canMove(next_x, next_y)) {
		for (int i = 0; i < 4; i++) {
			int nextdir = shark.priority[dir][i];
			next_x = x + direction[nextdir].first;
			next_y = y + direction[nextdir].second;
			if (inRange(next_x, next_y)) {
				if (map[next_x][next_y].num == num) {
					sharks[num].dir = nextdir;
					break;
				}
			}
		}
	}

	return { num, {next_x, next_y} };
}

 

 2. 이동할 좌표에 어떤 냄새도 없다면 이동, 아니라면 자신과 번호가 같거나 큰 곳인 경우 이동

void moveOne(int num, int next_x, int next_y) {
	
	if (map[next_x][next_y].num > 0) { 
		if (map[next_x][next_y].num >= num) { //쫒아냄
			map[next_x][next_y] = { num, K, true };
		}
	}
	else {
		map[next_x][next_y] = { num, K, true };
	}
}

 

3. 현재 상어가 존재하는 곳을 제외한 나머지 공간에 냄새가 남아있다면 -1을 하고 그러한 시간이 0이 되었다면 해당 좌표에 남아있던 상어의 번호를 삭제

for (int i = 0; i < N; i++) {
   for (int j = 0; j < N; j++) {
    	if (!map[i][j].exist && map[i][j].time > 0) {
      		if (--map[i][j].time == 0)
      			map[i][j] = { 0, 0, false };
      	}
    }
}

 

 이러한 과정이 1초 동안 일어나는 일 입니다. 마지막으로 매 초마다 격자에 1번 상어만 남아있는지 검사를 하게 된다면 문제를 해결할 수 있습니다. 

 

 

소스 코드

---

#include <iostream>
#include <vector>

using namespace std;

typedef struct mapInfo {
	int num, time;
	bool exist;
};

typedef struct sharkInfo {
	int dir;
	vector<vector<int>> priority;
};

pair<int, int> direction[4] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
mapInfo map[21][21];
vector<sharkInfo> sharks;
int N, M, K;

bool inRange(int x, int y) {
	return (0 <= x && x < N && 0 <= y && y < N);
}

bool canMove(int x, int y) {
	if (inRange(x,y)) 
		if (map[x][y].time == 0) 
			return true;
	return false;
}

pair<int, pair<int, int>> findNextCoord(int x, int y) {

	int num = map[x][y].num;
	sharkInfo shark = sharks[num];
	int dir = shark.dir;

	int next_x = x;
	int next_y = y;

	for (int i = 0; i < 4; i++) {
		int nextdir = shark.priority[dir][i];
		next_x = x + direction[nextdir].first;
		next_y = y + direction[nextdir].second;
		if (canMove(next_x, next_y)) {
			sharks[num].dir = nextdir;
			break;
		}
	}
	if (!canMove(next_x, next_y)) {
		for (int i = 0; i < 4; i++) {
			int nextdir = shark.priority[dir][i];
			next_x = x + direction[nextdir].first;
			next_y = y + direction[nextdir].second;
			if (inRange(next_x, next_y)) {
				if (map[next_x][next_y].num == num) {
					sharks[num].dir = nextdir;
					break;
				}
			}
		}
	}

	return { num, {next_x, next_y} };
}

void moveOne(int num, int next_x, int next_y) {
	
	if (map[next_x][next_y].num > 0) { 
		if (map[next_x][next_y].num >= num) { //쫒아냄
			map[next_x][next_y] = { num, K, true };
		}
	}
	else {
		map[next_x][next_y] = { num, K, true };
	}
}

int solve() {

	int cnt = -1;

	while (++cnt <= 1000) {

		vector<pair<int, pair<int, int>>> numAndCoords;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j].exist) {
					map[i][j].exist = false;
					numAndCoords.push_back(findNextCoord(i,j));
				}
			}
		}

		if (numAndCoords.size() == 1) 
			break;

		for (int i = 0; i < numAndCoords.size(); i++) {
			pair<int, pair<int, int>> elem = numAndCoords[i];
			moveOne(elem.first, elem.second.first, elem.second.second);
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!map[i][j].exist && map[i][j].time > 0) {
					if (--map[i][j].time == 0)
						map[i][j] = { 0, 0, false };
				}
			}
		}
	}

	return cnt = (cnt > 1000 ? -1 : cnt);
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M >> K;

	sharks.resize(M + 1);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int num; cin >> num;
			map[i][j].num = num;
			if (num > 0) {
				map[i][j].time = K;
				map[i][j].exist = true;
			}
		}
	}

	for (int i = 1; i <= M; i++) {
		cin >> sharks[i].dir;
		sharks[i].dir--;
	}
	
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < 4; j++) {
			vector<int> priority;
			for (int k = 0; k < 4; k++) {
				int dir; cin >> dir;
				priority.push_back(dir - 1);
			}
			sharks[i].priority.push_back(priority);
		}
	}

	cout << solve();
}