백준 19237 어른 상어
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상어 2상어 3상어 4↑↑↑↑↓↓↓↓←←←←→→→→
| ↓ ← ↑ → | ↓ → ← ↑ | → ← ↓ ↑ | ← → ↑ ↓ |
| → ↑ ↓ ← | ↓ ↑ ← → | ↑ → ← ↓ | ← ↓ → ↑ |
| ← → ↓ ↑ | ← → ↑ ↓ | ↑ ← ↓ → | ↑ → ↓ ← |
| → ← ↑ ↓ | → ↑ ↓ ← | ← ↓ ↑ → | ↑ → ↓ ← |
<표 1>
<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.
<그림 2>
<그림 3>
<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.
<그림 4>
<그림 5>
<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.
이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.
입력
첫 줄에는 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번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.
예제 입력 1
5 4 4
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3
예제 출력 1
14
[풀이 과정]
- smell_info arr[MAX][MAX] : 상어의 번호와 남은 냄새를 저장하는 구조체 배열
- vector <int> same_place[MAX][MAX] : 같은 위치에 상어가 있는지 판단하기 위한 벡터
- info shark[MAX * MAX] : M마리 상어의 정보를 저장하는 구조체 배열
- int direction[MAX * MAX][MAX][MAX] : 상어의 방향별 우선순위를 저장할 배열
1. 초기 상어의 위치를 입력받고 상어가 있는 칸은 번호와 냄새 K로 초기화한다.
2. 상어가 1마리 이상이면 반복문을 계속 실행한다.
- time이 1000이상이면 find를 false로 하고 -1을 출력한다.
- move_shark() : 상어를 이동시키는 함수
- remove_smell() : 냄새를 1 감소시키는 함수
- check_same_place() : 같은 위치에 상어가 있는지 확인하는 함수
- 반복문을 한 번 돌 때마다 time을 1 증가시킨다.
3. move_shark()
- 1~M번 상어 중 살아있는 상어를 이동시킨다.
- 각 상어별로 우선 순위에 주어진 방향의 다음 칸에 상어도 없고 남은 냄새도 없다면 can_move를 true로 바꾸고 same_place의 해당 위치에 상어의 번호를 push한다.
- 상어의 위치 정보를 업데이트한다.
- 4방향 모두 탐색했는데 이동 가능한 곳이 없다면 다시 4방향을 탐색하며 자신의 냄새가 있는 곳을 찾는다.
- 자신의 냄새가 있는 곳을 찾으면 same_place의 해당 위치에 번호를 push한다.
4. remove_smell()
- arr배열의 모든 위치를 탐색하면서 냄새가 있는 곳은 -1씩해준다.
5. check_same_place()
- sort함수를 활용해서 same_place[i][j]에 있는 상어의 번호들을 오름차순으로 정렬시킨다.
- same_place 전체를 탐색하면서 same_place[i][j][0]에 있는 상어의 번호를 arr[i][j].num에 넣고 냄새도 K로 초기화한다.
- 같은 위치에 또 다른 번호가 들어있다면 해당 상어는 dead를 true로 바꾸고 전체 상어의 수를 저장한 shark_num도 1 감소시킨다.
- 다음에 재사용을 위해 same_place[i][j]를 clear 해놓는다.
6. 반복문이 종료되고 find가 true이면 time을 false이면 -1을 출력한다.
[소스 코드]
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 25;
int N, M, K, shark_num;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
struct info {
int x, y, d;
bool dead;
};
struct smell_info {
int num, smell;
};
smell_info arr[MAX][MAX];
vector <int> same_place[MAX][MAX];
info shark[MAX * MAX];
int direction[MAX * MAX][MAX][MAX];
void remove_smell() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][j].num > 0) {
arr[i][j].smell--;
if (arr[i][j].smell == 0) arr[i][j].num = 0;
}
}
}
}
bool outofrange(int x, int y) {
if (x < 0 || x >= N || y < 0 || y >= N) return true;
return false;
}
void move_shark() {
for (int i = 1; i <= M; i++) {
if (shark[i].dead) continue;
int x = shark[i].x;
int y = shark[i].y;
int d = shark[i].d;
bool can_move = false;
for (int a = 0; a < 4; a++) {
int nd = direction[i][d][a];
int nx = x + dx[nd];
int ny = y + dy[nd];
if (outofrange(nx, ny)) continue;
if (arr[nx][ny].num == 0) {
can_move = true;
same_place[nx][ny].push_back(i);
shark[i].x = nx;
shark[i].y = ny;
shark[i].d = nd;
break;
}
}
if (can_move) continue;
for (int a = 0; a < 4; a++) {
int nd = direction[i][d][a];
int nx = x + dx[nd];
int ny = y + dy[nd];
if (outofrange(nx, ny)) continue;
if (arr[nx][ny].num == i) {
same_place[nx][ny].push_back(i);
shark[i].x = nx;
shark[i].y = ny;
shark[i].d = nd;
break;
}
}
}
}
void check_same_place() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sort(same_place[i][j].begin(), same_place[i][j].end());
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < same_place[i][j].size(); k++) {
if (k == 0) {
arr[i][j].num = same_place[i][j][k];
arr[i][j].smell = K;
}
else {
int num = same_place[i][j][k];
shark[num].dead = true;
shark_num--;
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
same_place[i][j].clear();
}
}
}
int main() {
scanf("%d %d %d", &N, &M, &K);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int a;
scanf("%d", &a);
arr[i][j].num = a;
if (a > 0) arr[i][j].smell = K;
else arr[i][j].smell = 0;
shark[a].x = i;
shark[a].y = j;
shark[a].dead = false;
}
}
int dir;
for (int i = 1; i <= M; i++) {
scanf("%d", &dir);
shark[i].d = dir - 1;
}
for (int i = 1; i <= M; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
int a;
scanf("%d", &a);
direction[i][j][k] = a - 1;
}
}
}
shark_num = M;
int time = 0;
bool find = true;
while (shark_num > 1) {
if (time >= 1000) {
find = false;
break;
}
move_shark();
remove_smell();
check_same_place();
time++;
}
if (find) printf("%d\n", time);
else printf("-1\n");
return 0;
}