문제 링크 : 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>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 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단계 : 4방향 검사
현재 상어를 방향을 기준으로 우선위에 따라 돌아가면서 다음 칸을 검사한다.
돌면서 내 냄새와 같은 칸이 나오면 그 값을 저장한다. 그리고 계속 검사한다. 왜냐하면 빈칸이고 냄새가 없는 칸이 나올수도 있기 때문이다. 후자의 경우가 더 우선순위가 높으므로 검사를 멈추면 안된다. (4방향 중 또 내 냄새와 같은 칸이 나오면 그 값은 그냥 건너 뛴다. 이미 우선순위에 의해 이동할 위치가 정해졌으므로)
돌면서 빈칸이고 냄새가 없는 칸이 나오면 현재 칸은 상어가 없는것으로 표시하고 이 경우가 가장 우선순위가 높으므로 다른 방향을 조사할 필요 없이 검사를 중단한다.
2단계
CASE 1
위에서 상어가 없고, 냄새도 없는 칸을 찾은 경우에는 해당 상어의 위치 정보를 바꿔주고(이차 배열은 아직 안바꿈), 임시 벡터를 만들어서 해당 칸에 상어 번호를 넣는다. (나중에 가장 작은 상어만 남겨놓고 다 내보내기 위함)
CASE 2
CASE1 에 해당하지 못할 경우에는 내냄새와 같은 칸으로 이동해야 한다. 1단계에서 값을 저장해놓았으므로 상어 객체 정보를 갱신한다.
CASE 3
이외 상황은 문제에서 조건으로 주어지지 않았으므로 고려하지 않아도 된다.
3단계
M개의 상어에 대해 어디 위치로 이동해야할지 조사가 다 끝났으니 정보를 갱신해야한다.
아까 위의 2단계-CASE1 에서 가장 번호가 작은 상어만 남겨놓고 나머지는 내보내는 것을 안 했으니 3단계에서 수행해준다. 임시 3차원 벡터 tmp를 돌면서 그 칸의 후보가 1이면 그냥 넣어주고, 2이상이면 상어 번호들을 비교해서 가장 최소 번호 상어만 남기고 다 지운다. (goOut()에서 수행한다.)
또한 내보낸 상어들 수를 카운트해서 처음 상어에서 빼준다.
4단계
이제 냄새를 1씩 감소해준다. 이때 주의할 점은 상어가 있는 칸을 제외하고 1을 감소시켜줘야 한다.
위 단계들을 반복하면서 남은 상어가 1마리인데 그 상어 번호가 1일 때까지 반복하며, 1000번 넘게 반복하면 스탑한다.
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
class Shark {
public:
int r, c, d;
int dirArr[5][5];
bool live;
Shark() {}
Shark(int _r, int _c, int _d, int _dirArr[5][5], bool _live) {
r = _r;
c = _c;
d = _d;
for (int i = 1; i <=4; i++) {
for (int j = 1; j<=4; j++) {
dirArr[i][j] = _dirArr[i][j];
}
}
live = _live;
}
};
pair<int, pair<int, int>> sharkMap[21][21]; //현재 상어 번호
Shark sharkArr[400];
int N, M, k;
//x, 위 아 왼 오
int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,-1,1 };
//1초 지나서 k감소
void decreaseK() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (sharkMap[i][j].first==-1 && sharkMap[i][j].second.second > 0) { //상어가 떠난 자리에 냄새가 남아있는 칸이면
sharkMap[i][j].second.second -= 1;
}
}
}
}
void goOut(vector<int> vec, int left, int nr, int nc) { //vec 중에서 left 빼고 다 내보내기
//sharkArr 처리
for (int i = 0; i < vec.size(); i++) {
if (vec[i] != left) { //나머지들 내보내기
sharkArr[vec[i]].live = false;
}
}
//sharkMap 처리
sharkMap[nr][nc] = make_pair(left, make_pair(left, k));
}
int main() {
cin >> N >> M >> k;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int sharkNum; cin >> sharkNum;
if (sharkNum != 0) {
sharkMap[i][j] = make_pair(sharkNum, make_pair(sharkNum, k));
sharkArr[sharkNum].r = i;
sharkArr[sharkNum].c = j;
sharkArr[sharkNum].live = true;
}
else {
sharkMap[i][j] = make_pair(-1, make_pair(-1, 0));
}
}
}
//상어 m 마리의 방향
for (int i = 1; i <= M; i++) {
int dir; cin >> dir;
sharkArr[i].d = dir;
}
//상어 m 마리의 우선순위
for (int m = 1; m <= M; m++) {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
cin >> sharkArr[m].dirArr[i][j];
}
}
}
int leftSharkCnt = M; //격자 안에 남아있는 상어 수
int sec = 0;
while (sec <= 1000) {
if (leftSharkCnt == 1 && sharkArr[1].live == true) break;
vector<int> tmp[21][21]; //움직이고나서의 상어 번호 저장
//상어 1번부터 M번까지 동시에 이동
for (int s = 1; s <= M; s++) {
if (sharkArr[s].live == false) continue; //이미 나간 상어
pair<int, int> sameSmellLoc = make_pair(-1, -1);
int toSameSmellmoveDir = 0;
int curR = sharkArr[s].r;
int curC = sharkArr[s].c;
int curD = sharkArr[s].d;
//아무것도 없는 빈 칸(k<=0) -> 자신의 냄새 있는 칸
bool isEmpty = false;
int nr, nc, nd;
//1단계
for (int i = 1; i <= 4; i++) {
nd = sharkArr[s].dirArr[curD][i];
nr = curR + dr[nd];
nc = curC + dc[nd];
if (nr <= 0 || nr > N || nc <= 0 || nc > N) continue;
if (sharkMap[nr][nc].first == -1 && sharkMap[nr][nc].second.second<=0) { //빈칸이고 냄새 없음
isEmpty = true;
sharkMap[curR][curC].first = -1; //현재칸 상어 없애기
break;
}
else if (sharkMap[nr][nc].second.second >= 0 && sharkMap[nr][nc].second.first == s) {
if (sameSmellLoc.first == -1) { //내냄새와 같은 첫 위치만 저장
sameSmellLoc.first = nr;
sameSmellLoc.second = nc;
toSameSmellmoveDir = nd;
}
}
}
//2단계
if (isEmpty == false) {
//위에서 저장한 내 냄새가 있는 칸으로 이동
sharkMap[sameSmellLoc.first][sameSmellLoc.second] = make_pair(s, make_pair(s, k));
sharkArr[s].r = sameSmellLoc.first;
sharkArr[s].c = sameSmellLoc.second;
sharkArr[s].d = toSameSmellmoveDir;
sharkMap[curR][curC].first = -1; //이동 후 현재 위치 있던거 삭제
}
else {
sharkArr[s].r = nr; sharkArr[s].c = nc; sharkArr[s].d = nd;
tmp[nr][nc].push_back(s); //일단 후보들 킵
}
}
//3단계
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (tmp[i][j].size() == 0) continue;
else if (tmp[i][j].size() == 1) {
int shark_num = tmp[i][j][0];
sharkMap[i][j] = make_pair(shark_num, make_pair(shark_num, k));
}
else { //2개 이상
int mini = 1000;
for (int k = 0; k < tmp[i][j].size(); k++) {
if (mini > tmp[i][j][k]) mini = tmp[i][j][k];
}
goOut(tmp[i][j], mini, i, j); //(i,j)에 mini번 상어만 남기기
leftSharkCnt = leftSharkCnt - tmp[i][j].size() + 1; //한개만 빼고 다 내보냄
}
}
}
//4단계
//상어 이동 완료 후
decreaseK();
//모든 상어 동시에 이동 후 sec 증가
sec++;
}
if (sec > 1000) cout << -1;
else cout << sec;
return 0;
}'Algorithm(삼성 코딩테스트 기출)' 카테고리의 다른 글
| [C++] 백준 19236번 - 청소년 상어(구현, DFS, 백트래킹) (0) | 2021.04.23 |
|---|---|
| [C++] 백준 17779번 - 게리맨더링 2 (구현, 삼성 코테 기출) (0) | 2021.04.22 |
| [C++] 백준 17142번 - 연구소 3 (BFS, 중복조합) (0) | 2021.04.22 |
| [C++] 백준 17143번 - 낚시왕 (구현, 시간초과 해결) (0) | 2021.04.21 |
