[BOJ/백준 19237/C++] 어른 상어
https://www.acmicpc.net/problem/19237
19237번: 어른 상어
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미
www.acmicpc.net
[문제 요약]
- 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다.
- 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.
- N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다.
- 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.
- 각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다.
- 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다.
- 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다.
- 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.
- 모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.
- 이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.
- 아래 <그림1>은 초기상태, <표1>은 각 상어별로 방향에 따른 우선순위이다.
- 그림5가 최종상태가 아니라 중간 상태임을 유의하자.
[문제 조건]
- 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)
- 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.
- 그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.
- 그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다.
- 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다.
- 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.
- 맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.
- 시간 제한 : 1초
- 메모리 제한 : 512MB
[문제 풀이]
이전에 풀었던 낚시왕(17143번), 청소년상어(19236번)와 같은 상어 시리즈의 다음 문제다.
이번 문제는 낚시왕 문제에서 조건이 몇가지 더 추가된 경우라 보면된다.
각 상어들은 움직일때마다 흔적을 남기면서 이동한다. 또한 상어들이 움직이는 방향은 우선적으로 빈칸으로 먼저 움직이고, 빈칸이 아예 없을 경우 흔적들 중 자신의 흔적의 방향으로 이동하게 된다. 확인하는 방향 순서는 문제에서 예제로 주어진 것과 같이 우선순위에 따라 확인하게 된다.
이번 문제는 조건이 많기때문에 천천히 차례대로 구현하는 방법과 주어지는 데이터를 가공하는 방법을 알아보자.
먼저 입력으로 주어지는 데이터부터 가공해보도록 하자.
typedef struct Shark
{
int num;
int dir;
pii pos;
}Shark;vector<vector<vector<Shark>>> mp;
vector<vector<pii>> trace;
vector<Shark> sharks;
vector<bool> dead_or_live;
vector<vector<vector<int>>> priority;
필자는 총 5개의 vector를 이용하였다.
mp배열은 각 위치별 상어들과 상어들의 수를 관리하기 위해 사용하였다.
trace배열은 각 흔적들을 관리하기 위해 사용하였다.
sharks배열은 각 상어들을 관리하는 배열이다.
dead_or_live는 인덱스가 각 상어들의 번호를 나타내고 죽었는지 살았는지 판별용으로 사용하였다.
priority 배열은 각 상어별로 우선순위를 저장하는 배열이다.
상어 정보 입력
//상어 정보
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int tmp;
cin >> tmp;
sharks[tmp].pos = { i,j };
mp[i][j].push_back({ tmp,-1, {i,j} });
}
}
for (int i = 1; i <= M; i++)
{
int direction;
cin >> direction;
sharks[i].num = i;
sharks[i].dir = direction;
mp[sharks[i].pos.first][sharks[i].pos.second][0].dir = direction;
}상어별 우선순위 입력
//우선순위
priority.resize(M + 1);
for (int i = 1; i <= M; i++)
{
priority[i].resize(5);
for (int j = 1; j <= 4; j++)
{
priority[i][j].resize(4);
for (int h = 0; h < 4; h++)
{
cin >> priority[i][j][h];
}
}
}
다음으로는 문제에서 1번 상어가 혼자 남을때까지 상어들은 계속 이동한다고 했고, 만약 1000초가 넘어가면 -1을 출력하면 된다.
for (int i = 1; i <= 1000; i++)
{
move_shark();
bool flag = false;
for (int j = 2; j <= M; j++)
{
if (dead_or_live[j]) { flag = true; break; }
}
if (!flag) { cout << i; return 0; }
}
cout << "-1";
다음은 이제 핵심이 되는 상어 이동 파트를 알아보자.
먼저 다시 정리해보면
- 상어는 현재 자신의 위치에 자신의 흔적을 남긴다.
- 우선순위에 따라 방향을 결정하고 그 위치로 이동한다.
- 한 위치에 상어가 2마리 이상이면 번호가 가장 낮은 상어만 살아남는다.
이때 죽은 상어들에 대해서는 흔적을 남기거나 이동을 일체 하지 않는다.
한 칸에 여러마리의 상어가 있을때 정렬기준은 번호가 작은 순선대로 정렬을 하고 첫번째 상어만 남긴채 모두 clear시켜준다.
void move_shark()
{
vector<vector<vector<Shark>>> tmp;
tmp.resize(N); for (int i = 0; i < N; i++) tmp[i].resize(N);
//흔적 남기기
for (int i = 1; i <= M; i++)
{
if (dead_or_live[i] == false) continue;
int cur_y = sharks[i].pos.first; int cur_x = sharks[i].pos.second;
trace[cur_y][cur_x] = { i,K };
}
//상어 이동
for (int i = 1; i <= M; i++)
{
if (dead_or_live[i] == false) continue;
int ndir = next_dir(i, sharks[i].pos);
int cur_y = sharks[i].pos.first; int cur_x = sharks[i].pos.second;
int next_y = cur_y + dy[ndir]; int next_x = cur_x + dx[ndir];
sharks[i].dir = ndir; sharks[i].pos = { next_y,next_x };
tmp[next_y][next_x].push_back(sharks[i]);
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
//흔적들 남은 시간 감소
if (trace[i][j].first != 0)
{
trace[i][j].second--;
if (trace[i][j].second == 0)
trace[i][j] = { 0,0 };
}
//번호가 가장 낮은 상어만 살아남는다.
if (tmp[i][j].size() > 1)
{
sort(tmp[i][j].begin(), tmp[i][j].end(), cmp);
Shark tmp2 = tmp[i][j][0];
for (int h = 1; h < tmp[i][j].size(); h++)
{
dead_or_live[tmp[i][j][h].num] = false;
}
tmp[i][j].clear(); tmp[i][j].push_back(tmp2);
}
}
}
mp = tmp;
}
이때 남은 방향을 결정 지어주는 함수 next_dir은 다음과 같다.
int next_dir(int shk_num, pii pos)
{
int cur_dir = sharks[shk_num].dir;
bool flag = false;
int ret = 0;
for (int i = 0; i < 4; i++)
{
int next_dir = priority[shk_num][cur_dir][i];
int nx = sharks[shk_num].pos.second + dx[next_dir];
int ny = sharks[shk_num].pos.first + dy[next_dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (trace[ny][nx].first == 0 && trace[ny][nx].second == 0) return next_dir;
else
{
if (trace[ny][nx].first == shk_num && !flag)
{
ret = next_dir; flag = true;
}
}
}
return ret;
}이때 리턴해주는 값은 최우선적으로 빈칸을 먼저 찾는다. 또한 빈칸이 없을 경우 4방향을 탐색하면서 자신의 번호와 같은 흔적을 가장 처음 발견할때의 방향을 리턴해준다.
[전체 소스 코드]
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define INF 987654321
#define mod 1000000
#define pii pair<int,int>
using namespace std;
typedef struct Shark
{
int num;
int dir;
pii pos;
}Shark;
int N, M, K;
int dx[5] = { 0,0,0,-1,1 };
int dy[5] = { 0,-1,1,0,0 };
vector<vector<vector<Shark>>> mp;
vector<vector<pii>> trace;
vector<Shark> sharks;
vector<bool> dead_or_live;
vector<vector<vector<int>>> priority;
bool cmp(Shark& a, Shark& b)
{
return a.num < b.num;
}
int next_dir(int shk_num, pii pos)
{
int cur_dir = sharks[shk_num].dir;
bool flag = false;
int ret = 0;
for (int i = 0; i < 4; i++)
{
int next_dir = priority[shk_num][cur_dir][i];
int nx = sharks[shk_num].pos.second + dx[next_dir];
int ny = sharks[shk_num].pos.first + dy[next_dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (trace[ny][nx].first == 0 && trace[ny][nx].second == 0) return next_dir;
else
{
if (trace[ny][nx].first == shk_num && !flag)
{
ret = next_dir; flag = true;
}
}
}
return ret;
}
void move_shark()
{
vector<vector<vector<Shark>>> tmp;
tmp.resize(N); for (int i = 0; i < N; i++) tmp[i].resize(N);
//흔적 남기기
for (int i = 1; i <= M; i++)
{
if (dead_or_live[i] == false) continue;
int cur_y = sharks[i].pos.first; int cur_x = sharks[i].pos.second;
trace[cur_y][cur_x] = { i,K };
}
//상어 이동
for (int i = 1; i <= M; i++)
{
if (dead_or_live[i] == false) continue;
int ndir = next_dir(i, sharks[i].pos);
int cur_y = sharks[i].pos.first; int cur_x = sharks[i].pos.second;
int next_y = cur_y + dy[ndir]; int next_x = cur_x + dx[ndir];
sharks[i].dir = ndir; sharks[i].pos = { next_y,next_x };
tmp[next_y][next_x].push_back(sharks[i]);
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
//흔적들 남은 시간 감소
if (trace[i][j].first != 0)
{
trace[i][j].second--;
if (trace[i][j].second == 0)
trace[i][j] = { 0,0 };
}
//번호가 가장 낮은 상어만 살아남는다.
if (tmp[i][j].size() > 1)
{
sort(tmp[i][j].begin(), tmp[i][j].end(), cmp);
Shark tmp2 = tmp[i][j][0];
for (int h = 1; h < tmp[i][j].size(); h++)
{
dead_or_live[tmp[i][j][h].num] = false;
}
tmp[i][j].clear(); tmp[i][j].push_back(tmp2);
}
}
}
mp = tmp;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> K;
mp.resize(N); trace.resize(N);
for (int i = 0; i < N; i++) { mp[i].resize(N); trace[i].resize(N); }
sharks.resize(M + 1); dead_or_live.resize(M + 1);
for (int i = 1; i <= M; i++) dead_or_live[i] = true;
//상어 정보
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int tmp;
cin >> tmp;
sharks[tmp].pos = { i,j };
mp[i][j].push_back({ tmp,-1, {i,j} });
}
}
for (int i = 1; i <= M; i++)
{
int direction;
cin >> direction;
sharks[i].num = i;
sharks[i].dir = direction;
mp[sharks[i].pos.first][sharks[i].pos.second][0].dir = direction;
}
//우선순위
priority.resize(M + 1);
for (int i = 1; i <= M; i++)
{
priority[i].resize(5);
for (int j = 1; j <= 4; j++)
{
priority[i][j].resize(4);
for (int h = 0; h < 4; h++)
{
cin >> priority[i][j][h];
}
}
}
for (int i = 1; i <= 1000; i++)
{
move_shark();
bool flag = false;
for (int j = 2; j <= M; j++)
{
if (dead_or_live[j]) { flag = true; break; }
}
if (!flag) { cout << i; return 0; }
}
cout << "-1";
}
굳