[백준 19237] 어른 상어 (C++)

A. 문제설명

www.acmicpc.net/problem/19237

19237번: 어른 상어

문제에 대한 자세한 설명은 링크 참조

 

1. 아래와 같은 N*N 배열판 위에 M마리의 상어가 주어짐

2. 각 상어는 1~M번 번호로 구분되어 초기 위치와 방향이 주어짐

3. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌림

4. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌림

5. 냄새는 상어가 k번 이동하고 나면 사라짐

6. 각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡으며 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡음

7. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따름(우선순위는 입력으로 주어짐)

8. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있음. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 됨

9. 모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨남

10. 3~9를 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하라

 

B. 접근법

시뮬레이션

 

기출문제 중 유독 자주 등장하는 상어 문제이다. 문제에서 주어진 조건이 많고 복잡해 보이지만 결국 풀이는 완전한 문제 독해로 요구된 사항들을 모두 구현하는 시뮬레이션으로 해결된다.

 

먼저, 문제에서 사용될 자료구조에 대해서 다음과 같이 정의해 주었다.

typedef struct{
  int n, sec; // n: 상어 냄새 번호, sec: 해당 냄새가 체류한 시간
  vector<int> sharks;
}ENTRY;
ENTRY arr[21][21] = {0, }; // 상어 냄새 체크 배열
bool deadCheck[441] = {0, }; // 상어 생존 체크 배열; 1일때 죽음

typedef struct{
  int x, y, dir;
}SHARK;
SHARK sharkPos[441];  // 상어 위치정보 배열
int priority[441][5][5] = {0, }; // 상어번호 1~M, 현재방향 1~4에서의, 방향정보 1~4
int dx[5] = {0, -1, 1, 0, 0}; // 1:상, 2:하, 3:좌, 4:우
int dy[5] = {0, 0, 0, -1, 1};

우선, 각 배열에 상어 냄새와 해당 냄새가 체류한 시간을 저장하고, 상어가 이동했을 때 겹쳐 여러마리가 들어가는 것까지 고려하여 벡터를 포함한 구조체인 ENTRY를 정의하고, N*N 배열로 선언하였다.

SHARK는 1~M번의 각 상어별 해당 위치와 현재 방향을 나타내는 구조체인데, M 크기의 배열로 선언하여 사용하고, 1~M번의 상어가 현재방향 1~4에서의 방향 우선순위 정보 1~4를 가지는 우선순위 배열을 priority로 선언하였다.

 

 

그리고 이 문제에 대해서 접근하자면 크게 3가지 부분으로 나누어 생각할 수 있다.

1. 상어가 냄새를 뿌리는 것

먼저 상어는 지금 막 이동한 위치에서 냄새를 해당 위치에 뿌려주어야 한다. 상어의 냄새는 k초후에 없어지는데, 매 초마다 이 냄새가 체류할 수 있는 잔여시간을 업데이트한다.

 

2. 문제설명 6/7의 상어 이동조건에 맞추어 다음 이동위치 선정

6. 각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡으며 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡음
7. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따름(우선순위는 입력으로 주어짐)

여기서, 문제에서 요구하는 사항들을 빠짐없이 잘 고려해주어야 하는데, 상하좌우 인접칸 중 냄새가 없는 칸이 있을 경우 해당 칸으로, 냄새가 없는 칸이 없을 경우 해당 상어의 냄새를 가진 칸으로 이동하여야 한다.

그런데, 만약 해당 조건을 만족하는 칸이 여러 개일 경우, 위에서 정의한 priority 배열에서 현재 상어번호가 현재 방향에서 가지는 우선순위 중 가장 높은 칸을 선택하도록 고려해 주어야한다.

 

3. 이동 후 같은 위치에 겹쳐진 상어 제거

마지막으로 상어가 냄새도 뿌리고, 문제 조건에 맞추어 다음 이동 위치도 알맞게 선정하여 이동완료하였다면, 해당 위치에 상어가 여러마리인 지 확인해주어야 하는데, 상어의 번호가 낮은 것이 생존하도록 구현한다.

하나의 위치에 상어 여러 마리가 들어와 있다면, 가장 낮은 번호 상어만 남기고 모두 제거하는 것이다.

 

C. 풀이

1. 각 상어는 이동한 칸에 냄새를 뿌리고, K초가 지난 냄새는 사라짐

2. 1~M번 상어까지 상어 카운트가 1보다 크거나 현재 시간이 1000초 이하면 반복

3. 각 상어는 인접칸 중 아무 냄새가 없는 칸(방향)을 찾아 벡터에 모은다.

4. 만약, 인접칸 중 그런 칸이 없다면 자신의 냄새가 있는 칸을 찾아 벡터에 모은다.

5. 2/3에서 벡터에 모은 방향이 하나인 경우 그대로 이동 진행

6. 만약 방향이 여러개라면, 해당 상어번호의 현재 방향을 기준으로 우선순위를 적용하여 우선순위 가장 높은 방향으로 이동

7. 이동 후, 만약 해당 칸에 상어가 존재한다면 해당 상어를 제거

 

D. 내 코드