알고리즘/[ADV] 삼성 SW 역량 테스트 A형
[코드트리] 메두사와 전사들 (삼성 SW 역량테스트 2024 하반기 오후 1번)
피로물든딸기
2024. 10. 20. 15:49
반응형
참고
- 코드트리 빵 (삼성 SW 역량테스트 2022 하반기 오후 1번)
- 메이즈 러너 (삼성 SW 역량테스트 2023 상반기 오후 1번)
https://www.codetree.ai/training-field/frequent-problems/problems/medusa-and-warriors
MAP의 크기는 MAX_N, 전사의 최대 수는 MAX_M, 도로가 아닌 곳은 WALL로 표기한다.
#define MAX_N (50 + 5)
#define MAX_M (300 + 30)
#define WALL (1)
메두사의 시야에 포함되는 정보는 다음과 같이 표기한다.
#define VISION (1) // 시야에 포함
#define WARRIOR (2) // 전사의 위치
#define SCOPE_WALL (3) // 가려진 전사에 의해 포함되지 않는 시야
#define STONE (4) // 석화된 전사
방향은 다음과 같이 정의한다.
#define UP (0)
#define DOWN (1)
#define LEFT (2)
#define RIGHT (3)
그 외 필요한 구조체와 변수는 다음과 같다.
int N, M;
int MAP[MAX_N][MAX_N];
bool visit[MAX_N][MAX_N]; // BFS 방문 체크
int scope[MAX_N][MAX_N]; // 메두사의 시선 처리
struct RC
{
int r;
int c;
};
RC start, end, medusa;
RC queue[MAX_N * MAX_N];
RC before[MAX_N][MAX_N]; // BFS 최단 경로 기록
RC position[MAX_N * MAX_N]; // 메두사의 경로
int pcnt; // 메두사의 경로 길이
struct RCW
{
int r;
int c;
bool dead;
};
RCW warrior[MAX_M];
struct ANSWER
{
int distance; // 모든 전사가 이동한 거리의 합
int stone; // 메두사로 인해 돌이 된 전사의 수
int attack; // 메두사를 공격한 전사의 수
};
ANSWER answer;
// ↑, ↓, ←, → (상, 하, 좌, 우)
int dr[] = { -1, 1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };
input은 다음과 같다.
문제의 좌표는 (0, 0)부터 입력되지만, 여기서는 (1, 1)부터 시작하도록 수정하였다.
void input()
{
int sr, sc, er, ec;
scanf("%d %d %d %d %d %d", &N, &M, &sr, &sc, &er, &ec);
start.r = sr + 1;
start.c = sc + 1;
end.r = er + 1;
end.c = ec + 1;
for (int m = 1; m <= M; m++) // 전사는 1번부터 시작
{
int r, c;
scanf("%d %d", &r, &c);
warrior[m].r = r + 1;
warrior[m].c = c + 1;
warrior[m].dead = false;
}
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scanf("%d", &MAP[r][c]);
}메두사의 이동
코드트리 빵을 참고하여, 메두사의 경로를 미리 구한다.
before 배열에 이전 좌표를 기록하면 경로를 기억할 수 있다.
void BFS()
{
int rp, wp;
int sr, sc, er, ec;
rp = wp = 0;
sr = start.r;
sc = start.c;
er = end.r;
ec = end.c;
queue[wp].r = sr;
queue[wp++].c = sc;
visit[sr][sc] = true;
before[sr][sc].r = -1;
before[sr][sc].c = -1;
while (rp < wp)
{
RC out = queue[rp++];
if (er == out.r && ec == out.c)
{
int tr = out.r;
int tc = out.c;
pcnt = 0;
position[pcnt].r = tr;
position[pcnt++].c = tc;
while (1)
{
// 이전 좌표
int br = before[tr][tc].r;
int bc = before[tr][tc].c;
if (br == sr && bc == sc) break;
position[pcnt].r = br;
position[pcnt++].c = bc;
tr = br;
tc = bc;
}
for (int i = 0; i < (pcnt / 2); i++)
{
RC tmp = position[i];
position[i] = position[pcnt - 1 - i];
position[pcnt - 1 - i] = tmp;
}
}
for (int i = 0; i < 4; i++)
{
int nr = out.r + dr[i];
int nc = out.c + dc[i];
if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
if (MAP[nr][nc] == WALL || visit[nr][nc] == true) continue;
queue[wp].r = nr;
queue[wp++].c = nc;
before[nr][nc].r = out.r; // 이전 좌표 기억
before[nr][nc].c = out.c;
visit[nr][nc] = true;
}
}
}
경로는 거꾸로 저장되므로, 경로 저장 후 position을 reverse하였다.
pcnt = 0;
position[pcnt].r = tr;
position[pcnt++].c = tc;
while (1)
{
// 이전 좌표
int br = before[tr][tc].r;
int bc = before[tr][tc].c;
if (br == sr && bc == sc) break;
position[pcnt].r = br;
position[pcnt++].c = bc;
tr = br;
tc = bc;
}
for (int i = 0; i < (pcnt / 2); i++)
{
RC tmp = position[i];
position[i] = position[pcnt - 1 - i];
position[pcnt - 1 - i] = tmp;
}
또한 최단 거리가 여러 개인 경우, 상 / 하 / 좌 / 우로 우선순위를 따르므로, 반드시 dr, dc 배열은 아래와 같이 정의해야 한다.
// ↑, ↓, ←, → (상, 하, 좌, 우)
int dr[] = { -1, 1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };
경로가 정해졌기 때문에 메두사는 턴 번호(p)를 입력받아서 현재 위치를 갱신할 수 있다.
이동 후, 모든 전사를 찾아서 같은 좌표에 있는 경우 dead = true로 처리한다.
void moveMedusa(int p)
{
// 한 칸 이동
medusa = position[p];
for (int m = 1; m <= M; m++)
{
if (warrior[m].dead == true) continue;
int r, c;
r = warrior[m].r;
c = warrior[m].c;
if (r == medusa.r && c == medusa.c)
warrior[m].dead = true;
}
}메두사의 시선
메두사는 상 / 하 / 좌 / 우 방향 중 전사를 가장 돌로 많이 변하는 방향으로 시선을 돌린다.
따라서 네 방향 모두 돌려서 해당 방향을 찾고, answer.stone에 정답을 기록한다.
void lookAt()
{
int maxValue, maxDir;
maxValue = maxDir = 0;
for (int i = 0; i < 4; i++)
{
int tmp = countStoneWarrior(i);
if (maxValue < tmp)
{
maxValue = tmp;
maxDir = i;
}
}
countStoneWarrior(maxDir);
answer.stone = maxValue;
}
countStoneWarrior는 다음과 같다.
- scope를 초기화한다.
- 살아있는 전사를 scope에 WARRIOR(2)로 표시한다.
- 메두사의 좌표와 넘겨받은 방향으로 직선 방향(straight)과 대각선 방향(diagonal)의 전사를 찾는다.
- 돌로 만든 전사의 수를 리턴한다.
- countStoneWarrior가 종료된 후, scope에 시야에 대한 정보가 남아 있게 된다.
+ scope가 초기화되고, 시야에 대한 정보가 남으므로,
lookAt에서 마지막에 countStoneWarrior(maxDir)를 한 번 더 호출하였다.
int countStoneWarrior(int dir)
{
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scope[r][c] = 0;
for (int m = 1; m <= M; m++)
{
if (warrior[m].dead == true) continue;
int r, c;
r = warrior[m].r;
c = warrior[m].c;
scope[r][c] = WARRIOR;
}
int mr, mc, count;
mr = medusa.r;
mc = medusa.c;
count = 0;
count += straight(mr, mc, dir);
count += diagonal(mr, mc, dir);
return count;
}
straight는 직선 방향만 찾는다.
이때, 석화된 전사의 위치는 4로 표시하고, 그 외 시야는 1로 표시한다.
그대로 구현하면 다음과 같다.
해당 방향으로 좌표를 갱신하면서, 범위를 벗어나면 break하고,
전사를 찾은 경우는 STONE(4)으로 마킹하고 그 좌표에 있는 전사의 수를 리턴한다.
그렇지 않은 경우는 VISION(1)으로 마킹한다.
int straight(int r, int c, int dir)
{
int sr, sc;
sr = r;
sc = c;
while (1)
{
int nr, nc;
nr = sr + dr[dir];
nc = sc + dc[dir];
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
if (scope[nr][nc] == WARRIOR)
{
scope[nr][nc] = STONE;
return getStoneCount(nr, nc);
}
scope[nr][nc] = VISION;
sr = nr;
sc = nc;
}
return 0;
}
하나의 좌표에 여러 전사들이 있을 수 있기 때문에, 살아있는 전사에 대해 같은 좌표의 전사를 모두 찾아야 한다.
int getStoneCount(int r, int c)
{
int count = 0;
for (int m = 1; m <= M; m++)
{
RCW w = warrior[m];
if (w.dead == true) continue;
if (r == w.r && c == w.c) count++;
}
return count;
}
대각선(diagonal)은 메두사의 좌표에서 해당되는 방향을 더한 좌표에 양 옆의 방향을 더한 좌표부터 탐색을 시작한다.
첫 번째 오른쪽은 메두사의 좌표 (row, col)에서
→ row + (dr[dir] + dr[nDir]), col + (dc[dir] + dc[nDir]) 부터 해당 방향으로 탐색을 시작한다.
두 번째 오른쪽 탐색은
row + (dr[dir] + dr[nDir]) * 2, col + (dc[dir] + dc[nDir]) * 2 부터 탐색한다.
그러다가 전사를 만나는 경우는 STONE(4)으로 마킹하고, 이후 대각선 영역은 탐색하지 못하게 SCOPE_WALL(3)로 마킹한다.
메두사의 방향이 상 / 하인 경우, 양 옆의 방향은 좌 / 우가 되고, 좌 / 우인 경우는 상 / 하가 된다.
makeStone에서 실제 석화된 전사의 수를 카운팅하고, scope를 위와 같이 갱신한다.
(nDir1과 nDir2로 나눠서 진행)
int diagonal(int r, int c, int dir)
{
int nDir1, nDir2;
if (dir < 2) // 상하
{
nDir1 = 2;
nDir2 = 3;
}
else
{
nDir1 = 0;
nDir2 = 1;
}
return makeStone(r, c, dir, nDir1) + makeStone(r, c, dir, nDir2);
}
makeStone은 다음과 같다.
- 첫 번째 while에서 대각선 시작 좌표를 찾은 후, 메두사의 방향대로 탐색을 시작한다. (경로를 벗어나면 break)
- 해당 좌표에 전사가 바로 있는 경우, STONE(4)으로 마킹하고, 남은 대각선은 SCOPE_WALL(3)로 마킹한다.
- straight에서 사용한 getStoneCount로 전사의 수를 누적한다. (하나의 좌표에 여러 명의 전사 존재)
- 전사가 없다면 VISION(1)으로 마킹하고 두 번째 while에서 직선 방향으로 탐색을 시작한다.
- 경계를 벗어나거나 다른 전사에 의해 시야가 막힌 경우(SCOPE_WALL)는 break로 빠져나간다.
- 전사를 찾은 경우, STONE(4)으로 마킹하고, 전사의 수를 누적(getStoneCount)한다.
- 그리고 다시 대각선 영역으로 SCOPE_WALL(3)로 마킹하고 break로 빠져나간다.
- 그렇지 않은 경우, VISION(1)으로 마킹한다.
int makeStone(int r, int c, int dir, int nDir)
{
int sr, sc;
int count, step;
sr = r;
sc = c;
count = 0;
step = 1;
while (1)
{
sr = r + (dr[dir] + dr[nDir]) * step;
sc = c + (dc[dir] + dc[nDir]) * step;
if (sr < 1 || sc < 1 || sr > N || sc > N) break;
if (scope[sr][sc] == WARRIOR)
{
scope[sr][sc] = STONE;
count += getStoneCount(sr, sc);
step++;
while (1)
{
sr += (dr[dir] + dr[nDir]);
sc += (dc[dir] + dc[nDir]);
if (sr < 1 || sc < 1 || sr > N || sc > N) break;
scope[sr][sc] = SCOPE_WALL;
}
break;
}
scope[sr][sc] = VISION;
while (1)
{
int nr, nc;
nr = sr + dr[dir];
nc = sc + dc[dir];
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
if (scope[nr][nc] == SCOPE_WALL) break;
if (scope[nr][nc] == WARRIOR)
{
scope[nr][nc] = STONE;
count += getStoneCount(nr, nc);
while (1)
{
nr += (dr[dir] + dr[nDir]);
nc += (dc[dir] + dc[nDir]);
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
scope[nr][nc] = SCOPE_WALL;
}
break;
}
scope[nr][nc] = VISION;
sr = nr;
sc = nc;
}
step++;
}
return count;
}전사들의 이동 / 공격
전사들은 메두사와의 거리를 줄일 수 있는 방향으로 한 칸 이동하고,
이런 방향이 두 개 이상일 경우 첫 번째 이동은 상 / 하 / 좌 / 우 우선순위로, 두 번째 이동은 좌 / 우 / 상 / 하 우선순위로 이동한다.
방향을 결정하는 방법은 메이즈 러너와 같고, 첫 번째 이동이냐 두 번째 이동이냐만 확인하면 된다.
void moveWarrior(bool first)
{
for (int m = 1; m <= M; m++)
{
RCW w = warrior[m];
if (w.dead == true) continue;
int direction = -1;
int upDown = checkRow(w);
int leftRight = checkCol(w);
// 메두사 방향으로 이동하므로 좌표를 벗어나지 않음.
if (first == true)
{
if (upDown < 0 && checkScope(w, UP) == true) direction = UP;
else if (upDown > 0 && checkScope(w, DOWN) == true) direction = DOWN;
else if (leftRight > 0 && checkScope(w, LEFT) == true) direction = LEFT;
else if (leftRight < 0 && checkScope(w, RIGHT) == true) direction = RIGHT;
}
else
{
if (leftRight > 0 && checkScope(w, LEFT) == true) direction = LEFT;
else if (leftRight < 0 && checkScope(w, RIGHT) == true) direction = RIGHT;
else if (upDown < 0 && checkScope(w, UP) == true) direction = UP;
else if (upDown > 0 && checkScope(w, DOWN) == true) direction = DOWN;
}
...
}
}
checkRow와 checkCol로 메두사의 위치와 현재 전사의 위치로 어느 방향으로 이동할지 결정한다. (메이즈 러너 참고)
int checkRow(RCW w)
{
int mr = medusa.r;
int wr = w.r;
// mr > wr -> 메두사는 아래에
// mr = wr -> 같은 행, 상하로 움직일 수 없음.
// mr < wr -> 메두사는 위에
return mr - wr;
}
int checkCol(RCW w)
{
int mc = medusa.c;
int wc = w.c;
// wc > mc -> 메두사는 왼쪽에
// wc = mc -> 같은 열, 좌우로 움직일 수 없음.
// wc < mc -> 메두사는 오른쪽에
return wc - mc;
}
checkScope에서 방향을 입력받은 후,
해당 전사가 석화된 경우, 다음 칸이 메두사의 시야거나, 석화된 전사가 있는 경우 false로 처리한다.
그 외는 움직일 수 있다. (석화된 전사가 있는 좌표도 메두사의 시야에 포함된다.)
bool checkScope(RCW w, int dir)
{
int wr, wc;
wr = w.r;
wc = w.c;
// 전사가 석화된 경우
if (scope[w.r][w.c] == STONE) return false;
int nr, nc;
nr = w.r + dr[dir];
nc = w.c + dc[dir];
// 다음 칸이 시야거나, 석화된 경우 (다른 전사가 석화된 경우도 시야에 포함)
if (scope[nr][nc] == VISION || scope[nr][nc] == STONE)
return false;
return true;
}
direciton이 -1이라면 움직일 수 없거나, 움직이더라도 메두사에서 멀어지는 방향이므로 continue로 넘어간다.
움직일 수 있는 방향에 메두사의 좌표와 같은 경우, 공격 횟수와 거리를 누적하고 사망 처리한다.
그 외에는 전사의 좌표를 갱신하고, 거리만 누적한다.
void moveWarrior(bool first)
{
for (int m = 1; m <= M; m++)
{
...
if (direction == -1) continue;
int nr, nc;
nr = w.r + dr[direction];
nc = w.c + dc[direction];
if (nr == medusa.r && nc == medusa.c)
{
answer.attack++;
answer.distance++;
warrior[m].dead = true;
continue;
}
warrior[m].r = nr;
warrior[m].c = nc;
answer.distance++;
}
}시뮬레이션
시뮬레이션은 다음과 같다.
메두사가 도착 위치로 이동하지 못하는 경우는 position이 갱신되지 않았을 테니, pcnt가 0이 된다. (-1 출력 후 종료)
마지막 도착 위치에서는 아무 것도 하지 않기 때문에 pcnt - 1까지 시뮬레이션을 반복한다.
- answer 초기화
- 메두사 이동
- 메두사 시선 처리 (scope 갱신)
- 전사들 이동 및 공격 첫 번째
- 전사들 이동 및 공격 두 번째
- 정답 출력
void simulate()
{
if (pcnt == 0)
{
printf("-1\n");
return;
}
for (int p = 0; p < pcnt - 1; p++)
{
answer.distance = answer.stone = answer.attack = 0;
moveMedusa(p);
lookAt();
moveWarrior(true);
moveWarrior(false);
printf("%d %d %d\n", answer.distance, answer.stone, answer.attack);
}
printf("%d\n", 0);
}
시뮬레이션 전에 main에서 BFS를 실행해서 메두사의 이동 경로를 찾으면 된다.
int main()
{
// scanf("%d", &T);
T = 1;
for (int tc = 1; tc <= T; tc++)
{
input();
BFS();
simulate();
}
return 0;
}전체 코드는 다음과 같다.
#include <stdio.h>
#define MAX_N (50 + 5)
#define MAX_M (300 + 30)
#define WALL (1)
#define VISION (1) // 시야에 포함
#define WARRIOR (2) // 전사의 위치
#define SCOPE_WALL (3) // 가려진 전사에 의해 포함되지 않는 시야
#define STONE (4) // 석화된 전사
#define UP (0)
#define DOWN (1)
#define LEFT (2)
#define RIGHT (3)
int T;
int N, M;
int MAP[MAX_N][MAX_N];
bool visit[MAX_N][MAX_N]; // BFS 방문 체크
int scope[MAX_N][MAX_N]; // 메두사의 시선 처리
struct RC
{
int r;
int c;
};
RC start, end, medusa;
RC queue[MAX_N * MAX_N];
RC before[MAX_N][MAX_N]; // BFS 최단 경로 기록
RC position[MAX_N * MAX_N]; // 메두사의 경로
int pcnt; // 메두사의 경로 길이
struct RCW
{
int r;
int c;
bool dead;
};
RCW warrior[MAX_M];
struct ANSWER
{
int distance; // 모든 전사가 이동한 거리의 합
int stone; // 메두사로 인해 돌이 된 전사의 수
int attack; // 메두사를 공격한 전사의 수
};
ANSWER answer;
// ↑, ↓, ←, → (상, 하, 좌, 우)
int dr[] = { -1, 1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };
void input()
{
int sr, sc, er, ec;
scanf("%d %d %d %d %d %d", &N, &M, &sr, &sc, &er, &ec);
start.r = sr + 1;
start.c = sc + 1;
end.r = er + 1;
end.c = ec + 1;
for (int m = 1; m <= M; m++) // 전사는 1번부터 시작
{
int r, c;
scanf("%d %d", &r, &c);
warrior[m].r = r + 1;
warrior[m].c = c + 1;
warrior[m].dead = false;
}
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scanf("%d", &MAP[r][c]);
}
void printMap(int map[MAX_N][MAX_N])
{
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
printf("%3d ", map[r][c]);
putchar('\n');
}
putchar('\n');
}
void printStatus()
{
int tmpMAP[MAX_N][MAX_N] = { 0 };
tmpMAP[medusa.r][medusa.c] = -1;
for (int m = 1; m <= M; m++)
{
if (warrior[m].dead == true) continue;
int r, c;
r = warrior[m].r;
c = warrior[m].c;
tmpMAP[r][c] = m;
}
printMap(tmpMAP);
}
void BFS()
{
int rp, wp;
int sr, sc, er, ec;
rp = wp = 0;
sr = start.r;
sc = start.c;
er = end.r;
ec = end.c;
queue[wp].r = sr;
queue[wp++].c = sc;
visit[sr][sc] = true;
before[sr][sc].r = -1;
before[sr][sc].c = -1;
while (rp < wp)
{
RC out = queue[rp++];
if (er == out.r && ec == out.c)
{
int tr = out.r;
int tc = out.c;
pcnt = 0;
position[pcnt].r = tr;
position[pcnt++].c = tc;
while (1)
{
// 이전 좌표
int br = before[tr][tc].r;
int bc = before[tr][tc].c;
if (br == sr && bc == sc) break;
position[pcnt].r = br;
position[pcnt++].c = bc;
tr = br;
tc = bc;
}
for (int i = 0; i < (pcnt / 2); i++)
{
RC tmp = position[i];
position[i] = position[pcnt - 1 - i];
position[pcnt - 1 - i] = tmp;
}
}
for (int i = 0; i < 4; i++)
{
int nr = out.r + dr[i];
int nc = out.c + dc[i];
if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
if (MAP[nr][nc] == WALL || visit[nr][nc] == true) continue;
queue[wp].r = nr;
queue[wp++].c = nc;
before[nr][nc].r = out.r; // 이전 좌표 기억
before[nr][nc].c = out.c;
visit[nr][nc] = true;
}
}
}
void moveMedusa(int p)
{
// 한 칸 이동
medusa = position[p];
for (int m = 1; m <= M; m++)
{
if (warrior[m].dead == true) continue;
int r, c;
r = warrior[m].r;
c = warrior[m].c;
if (r == medusa.r && c == medusa.c)
warrior[m].dead = true;
}
}
int getStoneCount(int r, int c)
{
int count = 0;
for (int m = 1; m <= M; m++)
{
RCW w = warrior[m];
if (w.dead == true) continue;
if (r == w.r && c == w.c) count++;
}
return count;
}
int straight(int r, int c, int dir)
{
int sr, sc;
sr = r;
sc = c;
while (1)
{
int nr, nc;
nr = sr + dr[dir];
nc = sc + dc[dir];
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
if (scope[nr][nc] == WARRIOR)
{
scope[nr][nc] = STONE;
return getStoneCount(nr, nc);
}
scope[nr][nc] = VISION;
sr = nr;
sc = nc;
}
return 0;
}
int makeStone(int r, int c, int dir, int nDir)
{
int sr, sc;
int count, step;
sr = r;
sc = c;
count = 0;
step = 1;
while (1)
{
sr = r + (dr[dir] + dr[nDir]) * step;
sc = c + (dc[dir] + dc[nDir]) * step;
if (sr < 1 || sc < 1 || sr > N || sc > N) break;
if (scope[sr][sc] == WARRIOR)
{
scope[sr][sc] = STONE;
count += getStoneCount(sr, sc);
step++;
while (1)
{
sr += (dr[dir] + dr[nDir]);
sc += (dc[dir] + dc[nDir]);
if (sr < 1 || sc < 1 || sr > N || sc > N) break;
scope[sr][sc] = SCOPE_WALL;
}
break;
}
scope[sr][sc] = VISION;
while (1)
{
int nr, nc;
nr = sr + dr[dir];
nc = sc + dc[dir];
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
if (scope[nr][nc] == SCOPE_WALL) break;
if (scope[nr][nc] == WARRIOR)
{
scope[nr][nc] = STONE;
count += getStoneCount(nr, nc);
while (1)
{
nr += (dr[dir] + dr[nDir]);
nc += (dc[dir] + dc[nDir]);
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
scope[nr][nc] = SCOPE_WALL;
}
break;
}
scope[nr][nc] = VISION;
sr = nr;
sc = nc;
}
step++;
}
return count;
}
int diagonal(int r, int c, int dir)
{
int nDir1, nDir2;
if (dir < 2) // 상하
{
nDir1 = 2;
nDir2 = 3;
}
else
{
nDir1 = 0;
nDir2 = 1;
}
return makeStone(r, c, dir, nDir1) + makeStone(r, c, dir, nDir2);
}
int countStoneWarrior(int dir)
{
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scope[r][c] = 0;
for (int m = 1; m <= M; m++)
{
if (warrior[m].dead == true) continue;
int r, c;
r = warrior[m].r;
c = warrior[m].c;
scope[r][c] = WARRIOR;
}
int mr, mc, count;
mr = medusa.r;
mc = medusa.c;
count = 0;
count += straight(mr, mc, dir);
count += diagonal(mr, mc, dir);
return count;
}
void lookAt()
{
int maxValue, maxDir;
maxValue = maxDir = 0;
for (int i = 0; i < 4; i++)
{
int tmp = countStoneWarrior(i);
if (maxValue < tmp)
{
maxValue = tmp;
maxDir = i;
}
}
countStoneWarrior(maxDir);
answer.stone = maxValue;
}
int checkRow(RCW w)
{
int mr = medusa.r;
int wr = w.r;
// mr > wr -> 메두사는 아래에
// mr = wr -> 같은 행, 상하로 움직일 수 없음.
// mr < wr -> 메두사는 위에
return mr - wr;
}
int checkCol(RCW w)
{
int mc = medusa.c;
int wc = w.c;
// wc > mc -> 메두사는 왼쪽에
// wc = mc -> 같은 열, 좌우로 움직일 수 없음.
// wc < mc -> 메두사는 오른쪽에
return wc - mc;
}
bool checkScope(RCW w, int dir)
{
int wr, wc;
wr = w.r;
wc = w.c;
// 전사가 석화된 경우
if (scope[w.r][w.c] == STONE) return false;
int nr, nc;
nr = w.r + dr[dir];
nc = w.c + dc[dir];
// 다음 칸이 시야거나, 석화된 경우 (다른 전사가 석화된 경우도 시야에 포함)
if (scope[nr][nc] == VISION || scope[nr][nc] == STONE)
return false;
return true;
}
void moveWarrior(bool first)
{
for (int m = 1; m <= M; m++)
{
RCW w = warrior[m];
if (w.dead == true) continue;
int direction = -1;
int upDown = checkRow(w);
int leftRight = checkCol(w);
// 메두사 방향으로 이동하므로 좌표를 벗어나지 않음.
if (first == true)
{
if (upDown < 0 && checkScope(w, UP) == true) direction = UP;
else if (upDown > 0 && checkScope(w, DOWN) == true) direction = DOWN;
else if (leftRight > 0 && checkScope(w, LEFT) == true) direction = LEFT;
else if (leftRight < 0 && checkScope(w, RIGHT) == true) direction = RIGHT;
}
else
{
if (leftRight > 0 && checkScope(w, LEFT) == true) direction = LEFT;
else if (leftRight < 0 && checkScope(w, RIGHT) == true) direction = RIGHT;
else if (upDown < 0 && checkScope(w, UP) == true) direction = UP;
else if (upDown > 0 && checkScope(w, DOWN) == true) direction = DOWN;
}
if (direction == -1) continue;
int nr, nc;
nr = w.r + dr[direction];
nc = w.c + dc[direction];
if (nr == medusa.r && nc == medusa.c)
{
answer.attack++;
answer.distance++;
warrior[m].dead = true;
continue;
}
warrior[m].r = nr;
warrior[m].c = nc;
answer.distance++;
}
}
void simulate()
{
if (pcnt == 0)
{
printf("-1\n");
return;
}
for (int p = 0; p < pcnt - 1; p++)
{
answer.distance = answer.stone = answer.attack = 0;
moveMedusa(p);
lookAt();
moveWarrior(true);
moveWarrior(false);
printf("%d %d %d\n", answer.distance, answer.stone, answer.attack);
}
printf("%d\n", 0);
}
int main()
{
// scanf("%d", &T);
T = 1;
for (int tc = 1; tc <= T; tc++)
{
input();
BFS();
simulate();
}
return 0;
}반응형