어흥
[백준 19237] 어른 상어 (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/19237
1. 주의할 점
- 순서대로 구현을 정확히 한다
- While문을 돌때마다 초기화를 잘 수행한다
- While문의 종료조건을 명확히 설정한다
- 매 TC마다 전역변수를 초기화한다 → 실제 시험에선 초기화한다
- 최대한 1시간이내로 풀려고 한다
2. 구현
- Info 구조체를 통해 상어에 대한 정보를 Shark[]에 담는다
- Info2 구조체를 통해 향수에 대한 정보를 Arr[][]에 담는다
- 이외의 배열들은 아래 주석 참고
- Make_flv() 함수를 통해 각 상어가 살아 있는 경우, 현재 자리에 자신의 향수를 남기는 과정을 수행한다
- Dev_flv() 함수를 통해 향수의 수명을 1씩 줄이며, 수명이 0이되면 해당 자리를 초기화한다
- CheckFin() 함수를 통해 1번 상어를 제외한 모든 상어가 죽거나 쫓겨났다면 True를 반환한다
- Mv_shark() 함수를 통해 죽이 않은 상어에 대해 움직임 or 정지를 수행한다. 이동된 자리에 여러마리의 상어가 존재하는 경우, AfterShkMv[][] 함수를 통해 번호가 적은 상어를 제외하곤 쫓겨나도록 설정한다
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct info{ //상어에 대한 정보
int x,y,dir;
bool dead = false;
};
struct info2{
int snum,len=0; //향수에 대한 정보
};
info tmp;
info shark[401];
int spd[401][5][4]; //[각 상어가][특정 방향일 때][상어의 탐색 방향 우선순위]
int num,sNum,len,val;
info2 arr[20][20]; //배열에서 향수에 대한 정보
int afterShkMv[20][20]; //상어가 움직인 뒤 -> 겹쳤을 때 대비해서 사용
int dx[5]={0,0,0,-1,1}; //상하좌우
int dy[5]={0,-1,1,0,0};
int curTime = 0;
void make_flv(){
for(int k=1;k<=sNum;k++){
if(shark[k].dead) continue; //죽은 경우 무시
arr[shark[k].y][shark[k].x].len = len;
arr[shark[k].y][shark[k].x].snum = k;
}
}
void mv_shark(){
//초기화
for(int i=0;i<num;i++)
for(int j=0;j<num;j++)
afterShkMv[i][j]=0;
int cx,cy,cd,nx,ny,nd;
for(int k=1;k<=sNum;k++){
if(shark[k].dead) continue; //죽은 경우 무시
int ownFlavor=-1;
cx = shark[k].x;
cy = shark[k].y;
cd = shark[k].dir;
bool moved = false;
for(int i=0;i<4;i++){
nd = spd[k][cd][i];
nx = cx + dx[nd];
ny = cy + dy[nd];
if(nx>=0 && ny>=0 && nx<num && ny<num){
if(arr[ny][nx].len==0){ //향이 없는 칸
shark[k].x = nx;
shark[k].y = ny;
shark[k].dir = nd;
moved = true;
break;
}
else{ //향이 있는 칸
if(arr[ny][nx].snum == k && ownFlavor==-1){ //자기 자신의 향수
ownFlavor = nd;
}
}
}
}
if(!moved && ownFlavor!=-1){ //자기 자신의 향수로 갈 수 있는 경우
nx = cx + dx[ownFlavor];
ny = cy + dy[ownFlavor];
shark[k].x = nx;
shark[k].y = ny;
shark[k].dir = ownFlavor;
}
}
//겹치는 경우 쫓겨남 표시
for(int k=1;k<=sNum;k++){
if(shark[k].dead) continue; //죽은 경우 무시
cx = shark[k].x;
cy = shark[k].y;
if(afterShkMv[cy][cx]!=0) shark[k].dead = true;
else
afterShkMv[cy][cx] = k;
}
}
void dec_flv(){
for(int i=0;i<num;i++)
for(int j=0;j<num;j++){
if(arr[i][j].len>0){
if(arr[i][j].len==1){
arr[i][j].len = 0;
arr[i][j].snum = 0;
}
else arr[i][j].len-=1;
}
}
}
bool checkFin(){
bool allDied = true;
for(int i=2;i<=sNum;i++)
if(!shark[i].dead){
allDied = false;
break;
}
return !shark[1].dead & allDied;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >>num>>sNum>>len;
for(int i=0;i<num;i++)
for(int j=0;j<num;j++){
cin>>val;
if(val!=0){
arr[i][j].snum = val;
shark[val].x = j;
shark[val].y = i;
}
}
for(int i=1;i<=sNum;i++)
cin>>shark[i].dir;
for(int i=1;i<=sNum;i++)
for(int j=1;j<5;j++)
for(int k=0;k<4;k++)
cin>>spd[i][j][k];
while(curTime<1001){
curTime++;
make_flv();
mv_shark();
dec_flv();
if(checkFin()) break;
}
curTime>1000 ? cout << -1 : cout<<curTime;
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 16940] BFS 스페셜 저지 (C++) (0) | 2021.04.13 |
---|---|
[백준 20056] 마법사 상어와 파이어볼 (C++) (0) | 2021.04.08 |
[백준 6059] Pasture Walking (C++) (0) | 2021.04.02 |
[백준 2479] 경로 찾기 (Java) (0) | 2021.04.02 |
[백준 14395] 4연산 (Java) (0) | 2021.04.02 |
Comments