어른 상어
문제 해석
NxN크기에 M마리 상어가 있을 때, 1번 상어만 남기까지 걸리는 시간을 구하는 문제입니다.
각 상어는 1초마다 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌립니다.
냄새는 상어가 K번 이동하고 나면 사라집니다.
각 상어가 이동방향을 정할 때, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡습니다.
그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡습니다.
가능한 칸이 여러개이면, 각 상어의 방향 우선순위를 따릅니다.
모든 상어가 이동한 후, 한 칸에 여러마리의 상어가 남아있으면 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫒겨납니다.
설계(20)
역시 삼성기출문제답게 생각해야하는 부분이 굉장히 많은 구현문제였습니다.
상어의 상태를 매번 체크하면서 조건에 부합하는 곳으로 이동시키는 방식으로 구현을 해야합니다.
그러기 위해서는 먼저 상어의 상태를 별도의 struct로 정의하였습니다. {x,y,방향,쫒겨났는지 여부}
다음으로 시간이 지날 때마다 냄새를 별도로 처리해주어야하지만, 저의 경우에는 각 arr에 {상어 번호, 현재시간+K}으로 구현해서 불필요하게 냄새를 감소시키지 않았습니다.
그리고 주의해야할 점 중 하나는 모든 상어의 이동을 마치고 arr에 갱신을 해야한다는 점입니다.
예를들어, 냄새가 없는곳으로 상어가 두마리 오는 것을 실시간으로 처리하면 한마리 상어가 먼저 냄새 없는 곳을 장악하고, 남은 한마리는 해당 구역 제외하고 냄새가 없는 곳을 따로 찾아서 가는 오류가 발생할 수 있기 때문입니다.
그리고 아주 큰 실수를 한부분이 있는데, 냄새가 4방향 전부 다 있는 경우,자신의 번호가 있는 냄새 구역으로 이동하는 부분이 여러개 있을 수 있다는 점입니다.
이 부분을 고려하지 않아서 디버깅을 하는데 오랜시간이 걸렸습니다.
위의 부분들을 주의해서 구현하고, 각 시간마다 쫒겨난 상어가 M-1인 경우 리턴해주면 됩니다.
구현(30)
코드1(Naive)
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 20
pair<int, int> arr[MAXN][MAXN];
struct node {
int x, y, dir, die;
};
node shark[MAXN * MAXN];
int N, M, K;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
vector<vector<vector<int> > > dirs;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int value;
cin >> value;
if (value) {
shark[value - 1] = { i,j,-1,0 };
arr[i][j] = { value - 1,K };
}
}
}
dirs.resize(M);
for (int i = 0; i < M; i++) {
int dir;
cin >> dir;
shark[i].dir = dir-1;
dirs[i].resize(4);
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
int dir;
cin >> dir;
dirs[i][j].push_back(dir-1);
}
}
}
int time = 0;
while (time < 1000) {
time++;
vector<node> tmp_shark(M);
for (int i = 0; i < M; i++) {
tmp_shark[i].die = shark[i].die;
if (shark[i].die) continue;
int x = shark[i].x;
int y = shark[i].y;
int dir = shark[i].dir;
bool flag = false;
int me_x = -1;
int me_y, me_dir;
for (int j = 0; j < 4; j++) {
int nx = x + dx[dirs[i][dir][j]];
int ny = y + dy[dirs[i][dir][j]];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (arr[nx][ny].second <= 0) {
tmp_shark[i] = { nx,ny,dirs[i][dir][j],shark[i].die };
flag = true;
break;
}
else if (arr[nx][ny].first == i && me_x ==-1) {
me_x = nx;
me_y = ny;
me_dir = dirs[i][dir][j];
}
}
if (!flag) {
tmp_shark[i] = { me_x,me_y,me_dir,shark[i].die };
}
}
for (int i = 0; i < M; i++) {
int x = tmp_shark[i].x;
int y = tmp_shark[i].y;
int dir = tmp_shark[i].dir;
int die = tmp_shark[i].die;
if (die) continue;
if (arr[x][y].second <= 0) {
shark[i] = tmp_shark[i];
arr[x][y] = { i,K + 1 };
}
else if (arr[x][y].first > i) {
shark[arr[x][y].first].die = 1;
tmp_shark[arr[x][y].first].die = 1;
shark[i] = tmp_shark[i];
arr[x][y] = { i,K + 1 };
}
else if (arr[x][y].first < i) {
shark[i].die = 1;
}
else {
shark[i] = tmp_shark[i];
arr[x][y] = { i,K + 1 };
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][j].second) {
arr[i][j].second--;
if (arr[i][j].second == 0) {
arr[i][j].first = 0;
}
}
}
}
int num = 0;
for (int i = 0; i < M; i++) {
if (shark[i].die) {
num++;
}
}
if (num == M - 1) {
cout << time << "\n";
return 0;
}
}
cout << "-1\n";
return 0;
}
처음에 Naive하게 생각하지 않고 바로 최적화방법으로 접근했다가 디버깅에 실패하여 처음부터 다시 Naive하게 짜본 코드입니다.
생각했던 논리대로 Naive하게 작성했는데도 테스트케이스가 안맞게 나와서 손으로 필기하면서 접근해보니 위에서 언급한(자신의 냄새가 있는 구역이 여러개 있을 수 있다)부분을 간과한 점을 파악할 수 있었습니다.
코드2(최적화)
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 20
struct node {
int x, y, dir, die;
};
pair<int, int> arr[MAXN][MAXN];
node shark[MAXN * MAXN];
vector<vector<vector<int> > > dirs;
int N, M, K;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> K;
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int value;
cin >> value;
if (value) {
shark[value-1] = { i,j,-1,false };
arr[i][j]= { value-1,K};
}
}
}
for (int i = 0; i < M; i++) {
int dir;
cin >> dir;
shark[i].dir = dir - 1;
}
dirs.resize(M);
for (int i = 0; i < M; i++) {
dirs[i].resize(4);
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
int dir;
cin >> dir;
dirs[i][j].push_back(dir - 1);
}
}
}
int time = 0;
while (time < 1000) {
time++;
vector<node> tmp_shark(M);
for (int i = 0; i < M; i++) {
int x = shark[i].x;
int y = shark[i].y;
int dir = shark[i].dir;
int die = shark[i].die;
if (die) {
tmp_shark[i].die = 1;
continue;
}
int me_x = -1;
int me_y;
bool flag = false;
int tmp_dir = -1;
for (int j = 0; j < 4; j++) {
int nx = x + dx[dirs[i][dir][j]];
int ny = y + dy[dirs[i][dir][j]];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (time > arr[nx][ny].second) {
tmp_shark[i] = { nx,ny,dirs[i][dir][j],0};
flag = true;
break;
}
else if (arr[nx][ny].first == i && me_x==-1){
me_x = nx;
me_y = ny;
tmp_dir = dirs[i][dir][j];
}
}
if (!flag) {
tmp_shark[i] = { me_x,me_y,tmp_dir,0 };
}
}
for (int i = 0; i < M; i++) {
int x = tmp_shark[i].x;
int y = tmp_shark[i].y;
int dir = tmp_shark[i].dir;
int die = tmp_shark[i].die;
if (die) continue;
if (time > arr[x][y].second) {
shark[i] = tmp_shark[i];
arr[x][y] = { i,time + K };
}
else if (i < arr[x][y].first) {
shark[arr[x][y].first].die = 1;
tmp_shark[arr[x][y].first].die = 1;
shark[i] = tmp_shark[i];
arr[x][y] = { i,time + K };
}
else if (i > arr[x][y].first){
shark[i].die = 1;
}
else {
shark[i] = tmp_shark[i];
arr[x][y] = { i,time + K };
}
}
int num = 0;
for (int i = 0; i < M; i++) {
if (shark[i].die) num++;
}
if (num == M - 1) {
cout << time << "\n";
return 0;
}
}
cout << "-1\n";
return 0;
}
Naive하게 작성하고 논리적 오류를 찾고나서 다시 최적화방법으로 구현해보았습니다.
잘못 설계된 부분만 바꾸니 바로 통과할 수 있었습니다.
time+K까지 냄새가 살아있는 점을 아이디어로 해서 별도로 냄새를 감소시키지 않고 풀이가 가능했습니다.
디버깅
제출결과
0 ms (Naive) 0 ms (최적화)
마무리
역시 삼성기출문제답다는 생각이 드는 문제였습니다. 별도의 알고리즘이 필요하지는 않지만 이렇게 단순하게 하라는데로 구현하는게 쉽지만은 않습니다. 이런 문제류는 가장 재미있으면서도 나중에 어떠한 코드를 작성할 때에도 도움이 될만한 문제들인 것 같습니다.