<Baekjoon> #19237 구현_어른 상어
🦈1. Struct 만들기
struct SHARK
정의
- 상어는 위치와 방향, 그리고 각 방향으로 향하고 있을 때마다 우선 순위 방향을 가지고 있다
- 같은 칸에 여러 상어가 있을 경우 가장 낮은 번호의 상어만 남기고 죽기 때문에 상어가 살아 있는지 아닌지 판단하는 변수 필요
struct SHARK { int y, x; int dir; int p[5][4]; bool alive = true; }; vector<SHARK> shark;
struct MAP_INFO
정의
- 상어들이 움직이고 난 후 한 칸에는 여러 상어가 있다
- 한 칸에는 상어가 뿌린 냄새와 냄새가 사라지기까지 남은 시간이 저장된다
struct MAP_INFO { vector<int> v; int scent_time=0; int scent_host=0; }; MAP_INFO map[MAX][MAX];
🦈2. Input Data
- 먼저 map의 정보를 받아오며 map에 상어의 번호를 저장하고 상어의 위치를 저장한다
- 각 map의 냄새의 주인을 저장하는 변수와 남은 시간은 0으로 초기화 한다
(이 부분을 생략하고 구조체를 선언할 때 초기화를 했더니 계속 오류가 났다)
//input shark position & scent
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int n; cin >> n;
if (n != 0) {
map[i][j].v.push_back(n);
shark[n].y = i;
shark[n].x = j;
}
map[i][j].scent_host = 0;
map[i][j].scent_time = 0;
}
}
- 다음으로 각 상어의 현재 방향을 입력 받는다
//input shark direction
for (int i = 1; i <= M; i++) {
int dir;
cin >> dir;
shark[i].dir = dir;
}
- 1번 상어부터 순서로 1,2,3,4번 방향일 때 이동하는 방향의 우선순위를 저장한다
//input shark's priority direction
for (int i = 1; i <= M; i++) {
for (int dir = 1; dir <= 4; dir++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
shark[i].p[dir][0] = a;
shark[i].p[dir][1] = b;
shark[i].p[dir][2] = c;
shark[i].p[dir][3] = d;
}
}
🦈3. Setting Smell
- 위에서 처음 map에 데이터를 입력할 때, 냄새의 주인과 냄새가 사라지기까지 남은 시간은 0으로 초기화를 해두었다
- 이 함수에서는 남은 냄새의 시간과 냄새의 주인을 업데이트 한다
- 살아있는 모든 상어가 움직인 위치를 조사해 해당 위치에 냄새와 냄새가 사라지기까지 남은 시간을 업데이트 한다
time
은 게임이 시작되고 흐른 시간을 나타내며scent_time
은 현재 시간 (time)을 기준으로k초
후까지만 유효하다
//time=current time
void setting_smell(int time) {
for (int i = 1; i <= M; i++) {
if (shark[i].alive == false) continue;
int y = shark[i].y;
int x = shark[i].x;
//현재 시간을 기준으로 k초 후 까지만 유효함
map[y][x].scent_time = time + K;
map[y][x].scent_host = i;
}
}
🦈4. Move Shark
- 먼저 맵의 각 칸에 있는 상어를 비워준다 (모든 살아있는 상어가 움직여서 새로운 칸으로 이동하기 때문)
for (int i = 1; i <= M; i++) {
if (shark[i].alive == false) continue;
int y = shark[i].y;
int x = shark[i].x;
map[y][x].v.clear();
}
- 인접한 네 칸중 아무 냄새가 없는 칸이 있는 경우 그 칸으로 이동
- 이동할 곳의 좌표가 (ny, nx)일 때,
if (map[ny][nx].scent_time<= time)
: 이동할 곳의 냄새의 시간이 현재 시간 time과 같거나 작다는 뜻은 이동 했을 때 해당 칸의 냄새는 사라진다는 의미이고 따라서 해당 칸은 빈 칸이 된다는 뜻이다
(상어가 모두 움직이고, 같은 칸에 있는 상어가 죽고 나서 1초가 된다. 처음에는 0초에서 시작한다) - 그런 칸이 없는 경우 현재 자신의 방향을 기준으로 우선순위가 높은 칸부터 탐색해서 자신의 냄새가 있는 칸에 넣어준다
- 위 탐색 과정을 동시에 진행해주고
bool flag
변수를 두어 인접한 아무 냄새가 없는 칸을 찾았을 경우에는true
로 바꾸어 준다 (자신의 냄새가 있는 칸으로 이동하지 않아도 된다는 의미로) - 인접한 아무 냄새가 없는 칸을 못 찾았을 경우에는 위에서 탐색을 할 때 같이 구해놓았던 근처에 있는 자신의 냄새가 있는 칸으로 이동한다
/*
2. 움직이려는 칸에 아무 냄새가 없는 경우,
자신의 냄새가 있는 경우를 동시에 조사하고
빈칸에 넣지 못했을 경우 자신의 냄새가 있는 칸에 넣어줌
*/
for (int i = 1; i <= M; i++) {
if (shark[i].alive == false) continue;
int y = shark[i].y;
int x = shark[i].x;
int dir = shark[i].dir;
int tmpX, tmpY, tmpD;
tmpX = tmpY = tmpD = -1;
bool flag = false;
for (int d = 0; d < 4; d++) {
//현재 방향 dir을 기준으로 d번째 우선 순위
int nDir = shark[i].p[dir][d];
int ny = y + dy[nDir];
int nx = x + dx[nDir];
if (ny <1 || nx < 1 || ny >N || nx > N) continue;
//scnet_time이 현재시간보다 작거나 같다는 뜻은 비었다는 뜻
if (map[ny][nx].scent_time<= time) {
flag = true;
map[ny][nx].v.push_back(i);
shark[i].y = ny;
shark[i].x = nx;
shark[i].dir = nDir;
break;
}
else {
//우선 순위가 높은 순으로 조사했을 때 자기 칸
if (map[ny][nx].scent_host == i) {
//자기보다 우선순위가 높은 방향에서 자기 칸을 아직 못 찾았을 경우
if (tmpX == -1) {
tmpY = ny;
tmpX = nx;
tmpD = nDir;
}
}
}
}
if (flag==false) {
map[tmpY][tmpX].v.push_back(i);
shark[i].y = tmpY;
shark[i].x = tmpX;
shark[i].dir = tmpD;
}
}
🦈5. Killing Shark
- 한 칸에 상어가 두 마리 이상인 경우 작은 상어만 살아남는다
- map[y][x].v에 있는 상어들의 번호를 정렬해 가장 앞에 있는 상어만 살리고 나머지는 죽인다
if (map[y][x].v.size() >= 2) {
sort(map[y][x].v.begin(), map[y][x].v.end());
int small = map[y][x].v[0];
for (int i = 1; i < map[y][x].v.size(); i++) {
int idx = map[y][x].v[i];
shark[idx].alive = false;
}
map[y][x].v.clear();
map[y][x].v.push_back(small);
map[y][x].scent_host = small;
}
Source Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 21;
int N, M, K;
int dy[] = {0, -1, 1, 0 ,0};
int dx[] = {0, 0,0, -1, 1};
struct SHARK {
int y, x;
int dir;
int p[5][4];
bool alive = true;
};
vector<SHARK> shark;
struct MAP_INFO {
vector<int> v;
int scent_time=0;
int scent_host=0;
};
MAP_INFO map[MAX][MAX];
//time=current time
void setting_smell(int time) {
for (int i = 1; i <= M; i++) {
if (shark[i].alive == false) continue;
int y = shark[i].y;
int x = shark[i].x;
//현재 시간을 기준으로 k초 후 까지만 유효함
map[y][x].scent_time = time + K;
map[y][x].scent_host = i;
}
}
void move_shark(int time) {
//1. 맵의 각 칸에 있는 상어를 비워줌
for (int i = 1; i <= M; i++) {
if (shark[i].alive == false) continue;
int y = shark[i].y;
int x = shark[i].x;
map[y][x].v.clear();
}
/*
2. 움직이려는 칸에 아무 냄새가 없는 경우,
자신의 냄새가 있는 경우를 동시에 조사하고
빈칸에 넣지 못했을 경우 자신의 냄새가 있는 칸에 넣어줌
*/
for (int i = 1; i <= M; i++) {
if (shark[i].alive == false) continue;
int y = shark[i].y;
int x = shark[i].x;
int dir = shark[i].dir;
int tmpX, tmpY, tmpD;
tmpX = tmpY = tmpD = -1;
bool flag = false;
for (int d = 0; d < 4; d++) {
//현재 방향 dir을 기준으로 d번째 우선 순위
int nDir = shark[i].p[dir][d];
int ny = y + dy[nDir];
int nx = x + dx[nDir];
if (ny <1 || nx < 1 || ny >N || nx > N) continue;
//scnet_time이 현재시간보다 작거나 같다는 뜻은 비었다는 뜻
if (map[ny][nx].scent_time<= time) {
flag = true;
map[ny][nx].v.push_back(i);
shark[i].y = ny;
shark[i].x = nx;
shark[i].dir = nDir;
break;
}
else {
//우선 순위가 높은 순으로 조사했을 때 자기 칸
if (map[ny][nx].scent_host == i) {
//자기보다 우선순위가 높은 방향에서 자기 칸을 아직 못 찾았을 경우
if (tmpX == -1) {
tmpY = ny;
tmpX = nx;
tmpD = nDir;
}
}
}
}
if (flag==false) {
map[tmpY][tmpX].v.push_back(i);
shark[i].y = tmpY;
shark[i].x = tmpX;
shark[i].dir = tmpD;
}
}
}
void killing_shark(int time) {
for (int i = 1; i <= M; i++) {
if (shark[i].alive == false) continue;
int y = shark[i].y;
int x = shark[i].x;
//한 칸에 상어 두 마리 이상인 경우 작은 상어만 살아 남음
if (map[y][x].v.size() >= 2) {
sort(map[y][x].v.begin(), map[y][x].v.end());
int small = map[y][x].v[0];
for (int i = 1; i < map[y][x].v.size(); i++) {
int idx = map[y][x].v[i];
shark[idx].alive = false;
}
map[y][x].v.clear();
map[y][x].v.push_back(small);
map[y][x].scent_host = small;
}
}
}
void input() {
cin >> N >> M >> K;
shark = vector<SHARK>(M+1);
//input shark position & scent
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int n; cin >> n;
if (n != 0) {
map[i][j].v.push_back(n);
shark[n].y = i;
shark[n].x = j;
}
map[i][j].scent_host = 0;
map[i][j].scent_time = 0;
}
}
//input shark direction
for (int i = 1; i <= M; i++) {
int dir;
cin >> dir;
shark[i].dir = dir;
}
//input shark's priority direction
for (int i = 1; i <= M; i++) {
for (int dir = 1; dir <= 4; dir++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
shark[i].p[dir][0] = a;
shark[i].p[dir][1] = b;
shark[i].p[dir][2] = c;
shark[i].p[dir][3] = d;
}
}
}
bool check_vaild() {
for (int i = 2; i <= M; i++)
if (shark[i].alive == true) return false;
return true;
}
int solution() {
int answer = -1;
for (int time = 0; time < 1001; time++) {
if (check_vaild()) {
answer = time;
break;
}
setting_smell(time);
move_shark(time);
killing_shark(time);
}
return answer;
}
int main() {
input();
cout<<solution()<<endl;
return 0;
}
Author And Source
이 문제에 관하여(<Baekjoon> #19237 구현_어른 상어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-19237-구현어른-상어저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)