백준 19237 - 어른 상어
문제링크
문제설명
- 구현, 시뮬레이션 문제
- 자세한 설명은 링크 참고
문제접근
- 구현, 시뮬레이션 문제는 모듈을 쪼개고, 구현된 모듈을 print 해서 직접 눈으로 확인하는 과정이 중요한 것 같다.
1. 문제의 입력 형식에 맞게 데이터를 받았는지 printInfo 함수로 확인한다.
- 격자에는 (상어 번호, 냄새 남은 시간) 정보가 담긴다.
board[row][col]은 (row, col) 에 위치하는 냄새의 번호와 남은 시간을 담는다. - 각 상어는 (번호, 방향) 을 가진다.
sharkInfo[row][col]는 (row, col) 에 위치하는 상어의 정보를 담도록 한다. - 상어는 방향전환을 할 때 특정 우선순위를 따른다. 우선순위는 상어마다 현재 방향(상, 하, 좌, 우)일 때의 우선순위가 각각 주어진다.
priroityInfo[shark][curDirection][0] ~ priroityInfo[shark][curDirection][3]은 해당 정보를 담도록 한다. - 입력과 동시(0초)에 상어는 해당 위치에 냄새를 뿌리므로
board에 업데이트 해준다.
2. 각 상어의 이동 방향을 결정한다.
- 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 여러 개인 경우 우선순위가 가장 높은 방향을 선택한다.
- 인접한 칸 중 아무 냄새가 없는 칸이 없다면 본인의 냄새가 있는 칸으로 방향을 잡는다. 여러 개인 경우 우선순위가 가장 높은 방향을 선택한다.
- 위 두가지 조건은 각 상어는 빈칸 혹은 본인 냄새가 있는 칸으로만 이동할 수 있다는 것을 의미한다. 따라서 한 칸에 여러 상어가 동시에 들어올 수 있는 경우는 해당 칸이 빈칸인 경우 뿐이다.
3. 모든 상어를 이동시킨다.
- 현재 보드에 남은 냄새의 시간은 모두 1 씩 줄어든다.
- 2번에서 설정한 이동 방향으로 모든 상어는 한 칸씩 움직인다.
- 모든 상어는 동시에 움직이기 때문에 움직인 결과가 반영된 격자와 원래 격자를 구분해야 한다.
4. 이동한 결과를 업데이트 해준다.
sharkInfo,board정보를 업데이트 해준다.- 하나의 칸에 여러 상어가 존재하는 경우 번호가 가장 작은 상어만 남긴다.
2 ~ 4번 과정을 최대 1000초까지 반복한다. 남은 상어의 수가 1인 경우는 1번 상어만 격자에 남아있다는 것을 의미하므로 그때까지 진행된 시간을 출력한다. 1000초를 넘어가는 경우 -1을 출력한다.
- time 초 후 상태를 비교하는 것이기 때문에 범위 설정을 0과 1000을 포함할 수 있도록 하였다. 초기 설정을 어떻게 하느냐에 따라 달라질 수 있다.
구현
#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>
#include <algorithm>
#define MAX_N 20
#define MAX_M 401
using namespace std;
int N, M, k;
pair<int, int> board[MAX_N][MAX_N]; // 칸에 위치한 냄새 정보 (first: 냄새, second: 남은 시간)
vector<pair<int, int>> sharkInfo[MAX_N][MAX_N]; // 각 좌표에 위치한 상어 정보 (first: 번호, second: 방향)
int priorityInfo[MAX_M][5][4]; // priorityInfo[shark][1][0] -> shark 가 위로 갈때 우선순위
int dx[5] = { 0, -1, 1, 0, 0 };
int dy[5] = { 0, 0, 0, -1, 1 };
int sharkNum;
void printInfo()
{
printf("-----------------------------------------------------------------\n");
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
{
if (sharkInfo[r][c].size() > 0)
{
for (int i = 0; i < sharkInfo[r][c].size(); i++)
{
printf("[%d, %d], shark: %d, direction: %d, ", r + 1, c + 1, sharkInfo[r][c][i].first, sharkInfo[r][c][i].second);
printf("direction priority: ");
for (int dir = 1; dir <= 4; dir++)
{
for (int j = 0; j < 4; j++)
{
printf("%d ", priorityInfo[sharkInfo[r][c][i].first][dir][j]);
}
printf(" / ");
}
printf("\n");
}
}
}
}
}
void printBoard()
{
printf("****************************************\n");
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
{
printf("[%d, %d] shark: %d, time: %d\n", r + 1, c + 1, board[r][c].first, board[r][c].second);
}
}
}
void UpdateMoveDirection(int cxpos, int cypos, int cdir)
{
vector<int> noSmellDirection;
vector<int> mySmellDirection;
int mySmell = sharkInfo[cxpos][cypos][0].first;
for (int dir = 1; dir <= 4; dir++)
{
int nXpos = cxpos + dx[dir];
int nYpos = cypos + dy[dir];
if (nXpos >= 0 && nXpos < N && nYpos >= 0 && nYpos < N)
{
if (board[nXpos][nYpos].first == 0)
{
noSmellDirection.push_back(dir);
}
else if (board[nXpos][nYpos].first == mySmell)
{
mySmellDirection.push_back(dir);
}
}
}
int shark = sharkInfo[cxpos][cypos][0].first;
int ndir = 0;
// 1. 아무 냄새가 없는 칸의 방향으로 잡는다.
if (noSmellDirection.size() > 0)
{
bool bflag = false;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < noSmellDirection.size(); j++)
{
if (priorityInfo[shark][cdir][i] == noSmellDirection[j])
{
ndir = noSmellDirection[j];
bflag = true;
break;
}
}
if (bflag) break;
}
}
else if (mySmellDirection.size() > 0)
{
bool bflag = false;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < mySmellDirection.size(); j++)
{
if (priorityInfo[shark][cdir][i] == mySmellDirection[j])
{
ndir = mySmellDirection[j];
bflag = true;
break;
}
}
if (bflag) break;
}
}
// Update Direction
sharkInfo[cxpos][cypos][0].second = ndir;
}
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
return p1.first < p2.first;
}
void MoveShark()
{
vector<pair<int, int>> newSharkInfo[MAX_N][MAX_N];
pair<int, int> nboard[MAX_N][MAX_N];
memcpy(nboard, board, sizeof(board));
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
{
// 칸에 남은 냄새 시간 1 감소
if (board[r][c].first > 0)
{
nboard[r][c].second = board[r][c].second - 1;
// 냄새가 사라지는 경우
if (nboard[r][c].second == 0)
{
nboard[r][c] = make_pair(0, 0);
}
}
// 새로운 칸으로 이동
if (sharkInfo[r][c].size() > 0)
{
int shark = sharkInfo[r][c][0].first;
int dir = sharkInfo[r][c][0].second;
int nx = r + dx[dir];
int ny = c + dy[dir];
newSharkInfo[nx][ny].push_back(make_pair(shark, dir));
nboard[nx][ny] = make_pair(shark, k);
}
}
}
// copy new -> before
// 같은 좌표에 여러 개의 상어가 온 경우
int count = 0;
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
{
sharkInfo[r][c].clear();
if (newSharkInfo[r][c].size() > 0)
{
sort(newSharkInfo[r][c].begin(), newSharkInfo[r][c].end(), cmp);
sharkInfo[r][c].push_back(newSharkInfo[r][c][0]);
nboard[r][c] = make_pair(sharkInfo[r][c][0].first, k);
count++;
}
}
}
memcpy(board, nboard, sizeof(nboard));
// printBoard();
sharkNum = count;
}
void SpendOneSecond()
{
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
{
if (sharkInfo[r][c].size() > 0)
{
int dir = sharkInfo[r][c][0].second;
UpdateMoveDirection(r, c, dir);
}
}
}
// printInfo();
MoveShark();
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> N >> M >> k;
memset(board, 0, sizeof(board));
sharkNum = M;
pair<int, int> sharkPos[MAX_M];
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
{
int val;
cin >> val;
if (val != 0)
{
sharkInfo[r][c].push_back(make_pair(val, 0));
sharkPos[val] = make_pair(r, c);
board[r][c] = make_pair(val, k);
}
}
}
for (int i = 1; i <= M; i++)
{
int dir;
cin >> dir;
int x = sharkPos[i].first;
int y = sharkPos[i].second;
sharkInfo[x][y][0].second = dir;
}
for (int shark = 1; shark <= M; shark++)
{
for (int cdir = 1; cdir <= 4; cdir++)
{
for (int i = 0; i < 4; i++)
{
int val;
cin >> val;
priorityInfo[shark][cdir][i] = val;
}
}
}
// printInfo();
int ans = -1;
for (int time = 0; time <= 1000; time++)
{
if (sharkNum == 1)
{
ans = time;
break;
}
// printf("time %d (sec)\n", time);
SpendOneSecond();
}
cout << ans << endl;
}
Leave a comment