코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, P, C, D;
int _y[] = { -1,1,0,0,-1,1,1,-1 }; //상하좌우↗시계방향
int _x[] = { 0,0,-1,1,1,1,-1,-1 };
int gameFlag = true;
#define diff(r1,c1,r2,c2) (r1-r2)*(r1-r2) + (c1-c2)*(c1-c2);
void printGame(vector<vector<int>> v)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << v[i][j] << " ";
}cout << endl;
}cout << endl;
}
int changeDir(int dir)
{
switch (dir)
{
case 0: return 1;
case 1: return 0;
case 2: return 3;
case 3: return 2;
default: return -1;
}
return -1;
}
bool compareDistance(pair<int, int> a, pair<int, int>b) // true : b(new santa) is more nearer than a
{
if (a.first == b.first)
{
return a.second < b.second ? 1 : 0;
}
return a.first < b.first ? 1 : 0;
}
int main()
{
cin >> N >> M >> P >> C >> D;
vector<vector<int>> game(N, vector<int>(N, -1)); // -1 : nothing, 1~30 : santa, 31 : rudolph
vector<pair<int, pair<int, int>>> santa(P, make_pair(0, make_pair(-1, -1))); //santa score, location(r,c)
vector<pair<int, int>> faint(P, make_pair(0, 0)); // M, 0 : live, 1 : faint, 2 : death
pair<int, pair<int, int>> rudolph; //rudolph score, location(r,c)
//rudolph location
int y, x, num;
cin >> y >> x;
rudolph.second.first = y - 1, rudolph.second.second = x - 1;
game[rudolph.second.first][rudolph.second.second] = 31;
for (int i = 0; i < P; i++)
{
cin >> num >> y >> x;
santa[num-1].second.first = y - 1, santa[num-1].second.second = x - 1;
game[santa[num - 1].second.first][santa[num - 1].second.second] = num - 1;
}
printGame(game);
while (gameFlag && M--) {
cout<<"============================"<<endl;
//rudolph moves
int attackNum = -1;
int attackDistance = (N - 1) * (N - 1);
pair<int, int> attackLocation;
for (int i = 0; i < P; i++)
{
//choose santa
if (faint[i].second != 2)
{
int distance = diff(rudolph.second.first, rudolph.second.second, santa[i].second.first, santa[i].second.second);
if (distance < attackDistance)
{
attackDistance = distance;
attackNum = i;
attackLocation = santa[i].second;
}
else if (distance == attackDistance)
{
if (compareDistance(attackLocation, santa[i].second))
{
attackDistance = distance;
attackNum = i;
attackLocation = santa[i].second;
}
}
}
}
//cout << "choose santa : " << attackNum << endl;
//rush
int standDis = attackDistance;
pair<int, int> moveLocation = make_pair(-1, -1);
for (int dir = 0; dir < 8; dir++)
{
int ry = rudolph.second.first + _y[dir], rx = rudolph.second.second + _x[dir];
if (ry >= N || rx >= N || ry < 0 || rx < 0) continue;
int distance = diff(ry, rx, santa[attackNum].second.first, santa[attackNum].second.second);
if (distance < standDis)
{
moveLocation = make_pair(ry, rx);
standDis = distance;
}
if (distance == 0) //crash
{
cout << "rudolph crash! " << attackNum << endl;
//faint
faint[attackNum] = make_pair(M, 1);
moveLocation = make_pair(ry, rx);
santa[attackNum].first += C;
int sy = santa[attackNum].second.first + C * _y[dir], sx = santa[attackNum].second.second + C * _x[dir];
int rush1Santa = attackNum;
while (1) {
if (sy >= N || sx >= N || sy < 0 || sx < 0) //out
{
faint[rush1Santa].second = 2;
game[santa[rush1Santa].second.first][santa[rush1Santa].second.second] = -1;
santa[rush1Santa].second = make_pair(-1, -1);
printGame(game);
break;
}
if (game[sy][sx] >= 0 && game[sy][sx] < 30) //interaction
{
int rush2Santa = game[sy][sx];
int ny = sy + _y[dir], nx = sx + _x[dir];
game[sy][sx] = rush1Santa;
santa[rush1Santa].second = make_pair(sy, sx);
sy = ny, sx = nx;
rush1Santa = rush2Santa;
printGame(game);
}
else
{
game[sy][sx] = rush1Santa;
santa[rush1Santa].second = make_pair(sy, sx);
printGame(game);
break;
}
}
break; //dont find directions anymore
}
}
game[rudolph.second.first][rudolph.second.second] = -1;
rudolph.second = moveLocation;
game[rudolph.second.first][rudolph.second.second] = 31;
printGame(game);
if (attackNum == -1) gameFlag = false; //every santa is dead
//santas move
int deadSanta = 0;
for (int i = 0; i < P; i++)
{
if (faint[i].second) { //dead of faint
if (faint[i].second == 1 && faint[i].first != M)
{
faint[i].second = 0;
}
else deadSanta++;
continue;
}
standDis = diff(rudolph.second.first, rudolph.second.second, santa[i].second.first, santa[i].second.second); //now located
int ny = santa[i].second.first, nx = santa[i].second.second;
int ndir = -1;
for (int dir = 0; dir < 4; dir++)
{
int sy = santa[i].second.first + _y[dir], sx = santa[i].second.second + _x[dir];
if (sy >= N || sx >= N || sy < 0 || sx < 0) continue;
if (game[sy][sx] >= 0 && game[sy][sx] < 30) continue;
int newDis = diff(rudolph.second.first, rudolph.second.second, sy, sx);
if (newDis < standDis)
{
ny = sy, nx = sx;
standDis = newDis;
ndir = dir;
}
}
if (make_pair(ny, nx) == santa[i].second) //can not move
continue;
if (standDis) //no crash, move santa
{
game[santa[i].second.first][santa[i].second.second] = -1;
santa[i].second = make_pair(ny, nx);
game[ny][nx] = i;
printGame(game);
continue;
}
//crash
cout << i << " crash!" << endl;
santa[i].first += D; //plus score
faint[i] = make_pair(M, 1);
int rush1Santa = i;
ny = ny += D * _y[changeDir(ndir)], nx += D * _x[changeDir(ndir)];
while (1) {
if (ny >= N || nx >= N || ny < 0 || nx < 0) //out
{
game[santa[rush1Santa].second.first][santa[rush1Santa].second.second] = -1;
faint[rush1Santa].second = 2;
santa[rush1Santa].second = make_pair(-1, -1);
deadSanta++;
printGame(game);
break;
}
if (game[ny][nx] >= 0 && game[ny][nx] < 30) //interaction
{
int rush2Santa = game[ny][nx];
int dy = ny + _y[changeDir(ndir)], dx = nx + _x[changeDir(ndir)];
if (game[santa[rush1Santa].second.first][santa[rush1Santa].second.second] == rush1Santa)
game[santa[rush1Santa].second.first][santa[rush1Santa].second.second] = -1;
game[ny][nx] = rush1Santa;
santa[rush1Santa].second = make_pair(ny, nx);
printGame(game);
ny = dy, nx = dx;
rush1Santa = rush2Santa;
}
else
{
if (game[santa[rush1Santa].second.first][santa[rush1Santa].second.second] == rush1Santa)
game[santa[rush1Santa].second.first][santa[rush1Santa].second.second] = -1;
game[ny][nx] = rush1Santa;
santa[rush1Santa].second = make_pair(ny, nx);
printGame(game);
break;
}
}
}
for (int p = 0; p < P; p++)
{
if (faint[p].second != 2) santa[p].first++;
}
if (deadSanta == P) gameFlag = false; //every santa is dead
printGame(game);
for (int i = 0; i < P; i++)
{
cout << santa[i].first << " ";
}cout << endl;
}
//output scores
for (int i = 0; i < P; i++)
{
cout << santa[i].first << " ";
}cout << endl;
return 0;
}
5 10 5 1 2
5 5
2 1 4
1 3 2
4 2 4
5 1 3
3 5 3
-1 -1 4 1 -1
-1 -1 -1 3 -1
-1 0 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 2 -1 31
============================
-1 -1 4 1 -1
-1 -1 -1 3 -1
-1 0 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 2 31 -1
-1 -1 4 1 -1
-1 -1 -1 3 -1
-1 -1 -1 -1 -1
-1 0 -1 -1 -1
-1 -1 2 31 -1
2 crash!
-1 -1 4 1 -1
-1 -1 -1 3 -1
-1 -1 -1 -1 -1
-1 0 -1 -1 -1
-1 2 -1 31 -1
-1 -1 4 1 -1
-1 -1 -1 -1 -1
-1 -1 -1 3 -1
-1 0 -1 -1 -1
-1 2 -1 31 -1
-1 -1 -1 1 -1
-1 -1 4 -1 -1
-1 -1 -1 3 -1
-1 0 -1 -1 -1
-1 2 -1 31 -1
-1 -1 -1 1 -1
-1 -1 4 -1 -1
-1 -1 -1 3 -1
-1 0 -1 -1 -1
-1 2 -1 31 -1
1 1 3 1 1
============================
-1 -1 -1 1 -1
-1 -1 4 -1 -1
-1 -1 -1 3 -1
-1 0 -1 -1 -1
-1 2 31 -1 -1
-1 -1 -1 1 -1
-1 -1 4 -1 -1
-1 -1 -1 3 -1
-1 -1 0 -1 -1
-1 2 31 -1 -1
-1 -1 -1 -1 -1
-1 -1 4 1 -1
-1 -1 -1 3 -1
-1 -1 0 -1 -1
-1 2 31 -1 -1
-1 -1 -1 -1 -1
-1 -1 4 1 -1
-1 -1 -1 -1 -1
-1 -1 0 3 -1
-1 2 31 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 -1 4 -1 -1
-1 -1 0 3 -1
-1 2 31 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 -1 4 -1 -1
-1 -1 0 3 -1
-1 2 31 -1 -1
2 2 4 2 2
============================
rudolph crash! 2
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 -1 4 -1 -1
-1 -1 0 3 -1
2 2 31 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 -1 4 -1 -1
-1 -1 0 3 -1
2 31 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 -1 4 -1 -1
-1 -1 -1 3 -1
2 31 0 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 4 1 -1
-1 -1 -1 3 -1
2 31 0 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 4 1 -1
-1 -1 3 -1 -1
2 31 0 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 4 -1 1 -1
-1 -1 3 -1 -1
2 31 0 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 4 -1 1 -1
-1 -1 3 -1 -1
2 31 0 -1 -1
3 3 6 3 3
============================
rudolph crash! 0
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 4 -1 1 -1
-1 -1 3 -1 -1
2 31 0 0 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 4 -1 1 -1
-1 -1 3 -1 -1
2 -1 31 0 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 4 -1 -1 -1
-1 -1 3 1 -1
2 -1 31 0 -1
3 crash!
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 4 3 -1 -1
-1 -1 -1 1 -1
2 -1 31 0 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 -1 -1
-1 4 -1 1 -1
2 -1 31 0 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 -1 -1
-1 4 -1 1 -1
2 -1 31 0 -1
5 4 7 6 4
============================
rudolph crash! 0
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 -1 -1
-1 4 -1 1 -1
2 -1 31 0 0
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 -1 -1
-1 4 -1 1 -1
2 -1 -1 31 0
1 crash!
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 1 -1
-1 4 -1 -1 -1
2 -1 -1 31 0
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 1 -1
-1 4 -1 -1 -1
-1 2 -1 31 0
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 1 -1
-1 -1 4 -1 -1
-1 2 -1 31 0
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 1 -1
-1 -1 4 -1 -1
-1 2 -1 31 0
7 7 8 7 5
============================
rudolph crash! 0
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 1 -1
-1 -1 4 -1 -1
-1 2 -1 31 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 1 -1
-1 -1 4 -1 -1
-1 2 -1 -1 31
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 1 -1
-1 -1 4 -1 -1
-1 -1 2 -1 31
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 1 -1
-1 -1 -1 4 -1
-1 -1 2 -1 31
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 3 1 -1
-1 -1 -1 4 -1
-1 -1 2 -1 31
8 8 9 8 6
============================
rudolph crash! 4
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 4 1 -1
-1 -1 -1 4 -1
-1 -1 2 -1 31
-1 -1 -1 -1 -1
-1 3 -1 -1 -1
-1 -1 4 1 -1
-1 -1 -1 4 -1
-1 -1 2 -1 31
-1 -1 -1 -1 -1
-1 3 -1 -1 -1
-1 -1 4 1 -1
-1 -1 -1 31 -1
-1 -1 2 -1 -1
1 crash!
-1 -1 -1 -1 -1
-1 3 -1 1 -1
-1 -1 4 -1 -1
-1 -1 -1 31 -1
-1 -1 2 -1 -1
-1 -1 -1 -1 -1
-1 3 -1 1 -1
-1 -1 4 -1 -1
-1 -1 2 31 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 3 4 -1 -1
-1 -1 2 31 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 3 4 -1 -1
-1 -1 2 31 -1
-1 -1 -1 -1 -1
8 11 10 9 8
============================
rudolph crash! 2
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 3 4 -1 -1
-1 2 2 31 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 3 4 -1 -1
-1 2 31 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 3 4 -1 -1
-1 2 31 -1 -1
-1 -1 -1 -1 -1
8 12 12 10 9
============================
rudolph crash! 2
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 3 4 -1 -1
2 2 31 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 3 4 -1 -1
2 31 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 3 4 1 -1
2 31 -1 -1 -1
-1 -1 -1 -1 -1
3 crash!
-1 -1 -1 -1 -1
-1 3 -1 -1 -1
-1 -1 4 1 -1
2 31 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 3 -1 -1 -1
-1 -1 -1 1 -1
2 31 4 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 3 -1 -1 -1
-1 -1 -1 1 -1
2 31 4 -1 -1
-1 -1 -1 -1 -1
8 13 14 13 10
============================
rudolph crash! 4
-1 -1 -1 -1 -1
-1 3 -1 -1 -1
-1 -1 -1 1 -1
2 31 4 4 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 3 -1 -1 -1
-1 -1 -1 1 -1
2 -1 31 4 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 3 -1 -1 -1
-1 -1 1 -1 -1
2 -1 31 4 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 3 -1 -1 -1
-1 -1 1 -1 -1
2 -1 31 4 -1
-1 -1 -1 -1 -1
8 14 15 14 12
8 14 15 14 12
C:\Users\김소현\source\repos\CodingTest\x64\Debug\CodingTest.exe(프로세스 41272개)이(가) 종료되었습니다(코드: 0개).
디버깅이 중지될 때 콘솔을 자동으로 닫으려면 [도구] -> [옵션] -> [디버깅] > [디버깅이 중지되면 자동으로 콘솔 닫기]를 사용하도록 설정합니다.
이 창을 닫으려면 아무 키나 누르세요...
'Coding Test' 카테고리의 다른 글
| [코드트리]메이즈 러너 2%실패 (0) | 2024.04.14 |
|---|---|
| [코드트리] 왕실의 기사 대결 (0) | 2024.04.13 |
| [코드트리] 문제 리스트(삼성기출) (1) | 2024.04.12 |
| [코드트리] 산타 선물 공장2(deque, priority_queue) - 시간초과 (0) | 2024.04.11 |
| [백준] 21736 헌내기는 친구가 필요해 (0) | 2024.04.11 |