BOJ 19237 : 어른 상어 - C++
어른 상어
코드
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0615 ~ 0810
int ans;
int dx[4] = {0, 0, -1, 1}; // 위 아래 왼쪽 오른쪽
int dy[4] = {-1, 1, 0, 0};
int board[25][25];
int t_board[25][25];
pair<int,int> pheromone[25][25]; // 상어 번호, 남은 시간
pair<int,int> t_pheromone[25][25];
struct shark{
int y;
int x;
int dir;
};
vector<int> shark_pri[4][410]; // dir,상어번호
vector<shark> shark_v(410); // 1번상어 -> 1번 인덱스
int N,M,k;
int saveDir(int d){
if(d > 3) d-=4;
if(d < 0) d+=4;
return d;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> k;
/* board정보 & 상어 위치 & 초기 페로몬 정보 저장 */
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
cin >> board[i][j];
if(board[i][j] == 0) continue;
shark_v[board[i][j]].y = i;
shark_v[board[i][j]].x = j;
pheromone[i][j] = {board[i][j], k}; // 최초 k만큼 지속
}
/* 상어의 최초 방향을 저장 */
for(int i=1;i<=M;i++)
{
int d;
cin >> d;
shark_v[i].dir = d-1;
}
/* 상어의 방향마다 우선순위를 받는다 */
for(int i=1;i<=M;i++)
{
for(int j=0;j<4;j++)
{
int p1,p2,p3,p4;
cin >> p1 >> p2 >> p3 >> p4;
shark_pri[j][i].push_back(p1-1);
shark_pri[j][i].push_back(p2-1);
shark_pri[j][i].push_back(p3-1);
shark_pri[j][i].push_back(p4-1);
}
}
while(true)
{
ans++;
/* 상어 이동 */
for(int i=1;i<=M;i++)
{
bool empty_space = false;
auto cur = shark_v[i];
if(cur.y == -1) continue;
for(int n=0;n<4;n++)
{
int ndir = shark_pri[cur.dir][i][n];
int ny = cur.y + dy[ndir];
int nx = cur.x + dx[ndir];
if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
if(pheromone[ny][nx].second > 0) continue;
// 내가 갈 곳에 이미 상어가 있는데 내가 더 번호가 크면 나는 집에 가야함
if(t_board[ny][nx] != 0 and t_board[ny][nx] < i){
empty_space = true;
shark_v[i].y = -1;
shark_v[i].x = -1;
shark_v[i].dir = -1;
break;
}
t_pheromone[ny][nx] = {i, k};
shark_v[i].y = ny;
shark_v[i].x = nx;
shark_v[i].dir = ndir;
t_board[ny][nx] = i;
empty_space = true;
break;
}
if(empty_space == true) continue;
/* 페로몬이 없는칸이 없으므로 우선순위에 따라 내 페로몬이 있는 곳으로 이동 */
for(int n=0;n<4;n++)
{
int ndir = shark_pri[cur.dir][i][n]; // 우선순위에 따르는 특별한 dir
int ny = cur.y + dy[ndir];
int nx = cur.x + dx[ndir];
if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
if(pheromone[ny][nx].first != i) continue; // 내 페로몬이 없으면 pass
t_pheromone[ny][nx] = {i, k};
shark_v[i].y = ny;
shark_v[i].x = nx;
shark_v[i].dir = ndir;
t_board[ny][nx] = i;
break;
}
}
/* t_pheromone -> pheromone 으로 이동 */
/* 페로몬 감소 */
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(pheromone[i][j].second == 0) continue;
pheromone[i][j].second--;
if(pheromone[i][j].second == 0)
pheromone[i][j] = {0, 0};
}
/* 새롭게 추가된 페로몬을 복사 */
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(t_pheromone[i][j].second == 0) continue;
pheromone[i][j] = t_pheromone[i][j];
t_pheromone[i][j] = {0,0}; // 초기화
}
/* t_board -> board로 이동 */
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
board[i][j] = t_board[i][j];
t_board[i][j] = 0;
}
/* 1번 상어만 남았는지 검사 */
int cnt=0;
for(int i=1;i<=M;i++)
if(shark_v[i].y != -1) cnt++;
if(cnt == 1) break;
else if(ans >= 1000){
ans = -1;
break;
}
}
cout << ans;
return 0;
}
- 핵심
동시에 일어나는 일
이기 때문에 비어있는 임시배열
을 이용
하는 것
: board[][]
와 pheromone[][]
으로 비교
t_board[][]
와 t_pheromone[][]
에 저장
상어의 정보
를 응집
하기 위해 shark 구조체
사용
- 이상한 점
: 해당 문제에서 1000이 넘으면 종료
된다고 문제에 나와있으나 1000이 되어도 -1로 처리
를 해야함
--> 많은 사람들이 이것으로 오답처리
됨
Author And Source
이 문제에 관하여(BOJ 19237 : 어른 상어 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-19237-어른-상어-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <cstdio> #include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #include <set> #include <deque> #include <numeric> #include <map> #define ll long long using namespace std; // 0615 ~ 0810 int ans; int dx[4] = {0, 0, -1, 1}; // 위 아래 왼쪽 오른쪽 int dy[4] = {-1, 1, 0, 0}; int board[25][25]; int t_board[25][25]; pair<int,int> pheromone[25][25]; // 상어 번호, 남은 시간 pair<int,int> t_pheromone[25][25]; struct shark{ int y; int x; int dir; }; vector<int> shark_pri[4][410]; // dir,상어번호 vector<shark> shark_v(410); // 1번상어 -> 1번 인덱스 int N,M,k; int saveDir(int d){ if(d > 3) d-=4; if(d < 0) d+=4; return d; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M >> k; /* board정보 & 상어 위치 & 초기 페로몬 정보 저장 */ for(int i=0;i<N;i++) for(int j=0;j<N;j++) { cin >> board[i][j]; if(board[i][j] == 0) continue; shark_v[board[i][j]].y = i; shark_v[board[i][j]].x = j; pheromone[i][j] = {board[i][j], k}; // 최초 k만큼 지속 } /* 상어의 최초 방향을 저장 */ for(int i=1;i<=M;i++) { int d; cin >> d; shark_v[i].dir = d-1; } /* 상어의 방향마다 우선순위를 받는다 */ for(int i=1;i<=M;i++) { for(int j=0;j<4;j++) { int p1,p2,p3,p4; cin >> p1 >> p2 >> p3 >> p4; shark_pri[j][i].push_back(p1-1); shark_pri[j][i].push_back(p2-1); shark_pri[j][i].push_back(p3-1); shark_pri[j][i].push_back(p4-1); } } while(true) { ans++; /* 상어 이동 */ for(int i=1;i<=M;i++) { bool empty_space = false; auto cur = shark_v[i]; if(cur.y == -1) continue; for(int n=0;n<4;n++) { int ndir = shark_pri[cur.dir][i][n]; int ny = cur.y + dy[ndir]; int nx = cur.x + dx[ndir]; if(nx<0 or ny<0 or nx>=N or ny>=N) continue; if(pheromone[ny][nx].second > 0) continue; // 내가 갈 곳에 이미 상어가 있는데 내가 더 번호가 크면 나는 집에 가야함 if(t_board[ny][nx] != 0 and t_board[ny][nx] < i){ empty_space = true; shark_v[i].y = -1; shark_v[i].x = -1; shark_v[i].dir = -1; break; } t_pheromone[ny][nx] = {i, k}; shark_v[i].y = ny; shark_v[i].x = nx; shark_v[i].dir = ndir; t_board[ny][nx] = i; empty_space = true; break; } if(empty_space == true) continue; /* 페로몬이 없는칸이 없으므로 우선순위에 따라 내 페로몬이 있는 곳으로 이동 */ for(int n=0;n<4;n++) { int ndir = shark_pri[cur.dir][i][n]; // 우선순위에 따르는 특별한 dir int ny = cur.y + dy[ndir]; int nx = cur.x + dx[ndir]; if(nx<0 or ny<0 or nx>=N or ny>=N) continue; if(pheromone[ny][nx].first != i) continue; // 내 페로몬이 없으면 pass t_pheromone[ny][nx] = {i, k}; shark_v[i].y = ny; shark_v[i].x = nx; shark_v[i].dir = ndir; t_board[ny][nx] = i; break; } } /* t_pheromone -> pheromone 으로 이동 */ /* 페로몬 감소 */ for(int i=0;i<N;i++) for(int j=0;j<N;j++) { if(pheromone[i][j].second == 0) continue; pheromone[i][j].second--; if(pheromone[i][j].second == 0) pheromone[i][j] = {0, 0}; } /* 새롭게 추가된 페로몬을 복사 */ for(int i=0;i<N;i++) for(int j=0;j<N;j++) { if(t_pheromone[i][j].second == 0) continue; pheromone[i][j] = t_pheromone[i][j]; t_pheromone[i][j] = {0,0}; // 초기화 } /* t_board -> board로 이동 */ for(int i=0;i<N;i++) for(int j=0;j<N;j++) { board[i][j] = t_board[i][j]; t_board[i][j] = 0; } /* 1번 상어만 남았는지 검사 */ int cnt=0; for(int i=1;i<=M;i++) if(shark_v[i].y != -1) cnt++; if(cnt == 1) break; else if(ans >= 1000){ ans = -1; break; } } cout << ans; return 0; }
- 핵심
동시에 일어나는 일
이기 때문에비어있는 임시배열
을이용
하는 것
:board[][]
와pheromone[][]
으로비교
t_board[][]
와t_pheromone[][]
에저장
상어의 정보
를응집
하기 위해shark 구조체
사용
- 이상한 점
: 해당 문제에서1000이 넘으면 종료
된다고 문제에 나와있으나1000이 되어도 -1로 처리
를 해야함
--> 많은 사람들이 이것으로오답처리
됨
Author And Source
이 문제에 관하여(BOJ 19237 : 어른 상어 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-19237-어른-상어-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)