[코드트리] 토끼와 경주 (삼성 SW 역량테스트 2023 상반기 오전 2번, B형)
2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,
A형 1문제 + B형 문제 1문제가 출제됩니다.
참고
- B형 필수 : 우선순위 큐 Priority Queue
https://www.codetree.ai/training-field/frequent-problems/problems/rabit-and-race
2차원 좌표 N x M이 100,000 * 100,000이다. → 2차원 배열 선언 시, 메모리 초과
토끼가 움직이는 거리 d <= 1,000,000,000 → d 만큼 움직이면 시간 초과
따라서, 토끼 구조체에서 좌표를 관리하고, 효율적으로 움직여야 한다.
좌표를 관리할 구조체와 토끼를 관리할 구조체를 선언한다.
typedef long long ll;
typedef struct st1
{
int r;
int c;
}RC;
typedef struct st2
{
int r;
int c;
int id;
int d;
int check;
int jumpCount;
ll score;
}RABBIT;
main은 다음과 같다.
typedef long long ll;
#define START (100)
#define RACE (200)
#define CHANGE (300)
#define SELECT (400)
...
int main(void)
{
scanf("%d", &Q);
for (int q = 0; q < Q; q++)
{
scanf("%d", &COMMAND);
if (COMMAND == START) input();
else if (COMMAND == RACE)
{
int k, s;
scanf("%d %d", &k, &s);
race(k, s);
}
else if (COMMAND == CHANGE)
{
int pid_t, l;
scanf("%d %d", &pid_t, &l);
change(pid_t, l);
}
else if (COMMAND == SELECT)
{
select();
}
}
return 0;
}우선순위 큐
경주는 최대 2,000번, 한 경주 당 최대 100번 반복하고 2,000마리의 토끼 중 우선순위가 높은 토끼를 구해야 한다.
완전 탐색으로 토끼를 선택할 경우, 2,000 * 100 * 2,000 = 400,000,000 = 4억이므로 역시 시간 초과다.
따라서 우선순위 큐를 구현해야 한다.
C++의 priority_queue 대신 배열로 직접 구현하면 토끼의 점수를 계산하기 편하고, 디버깅도 쉽다.
우선순위 큐의 직접 구현은 B형 필수 : 우선순위 큐 Priority Queue와 BOJ 10825 : 국영수를 참고하자.
토끼에 대한 우선순위 큐 push, pop은 다음과 같다.
RABBIT heap[MAX];
int hn;
RABBIT pop()
{
RABBIT ret, tmp;
ret = heap[1];
heap[1] = heap[hn];
heap[hn].jumpCount = 0x7fff0000;
heap[hn].r = 100001; // r + c = overflow 방지를 위해 0x7fff0000을 사용하지 않음.
heap[hn].c = 100001;
heap[hn--].id = 0x7fff0000;
for (register int i = 1; i * 2 <= hn;)
{
if (isMinRabbit(heap[i], heap[i * 2]) && isMinRabbit(heap[i], heap[i * 2 + 1])) break;
else if (isMinRabbit(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
i = i * 2 + 1;
}
}
return ret;
}
void push(RABBIT x)
{
RABBIT tmp;
heap[++hn] = x;
for (int i = hn; i > 1; i /= 2)
{
if (isMinRabbit(heap[i / 2], heap[i])) return;
tmp = heap[i / 2];
heap[i / 2] = heap[i];
heap[i] = tmp;
}
}
토끼를 선택하기 위한 우선순위는 isMinRabbit에서 결정된다.
문제에서 주어진 우선순위 조건을 순서대로 구현하면 된다.
int isMinRabbit(RABBIT a, RABBIT b)
{
// 1. 점프 횟수가 적은 토끼
if (a.jumpCount != b.jumpCount) return a.jumpCount < b.jumpCount;
// 2. 현재 서 있는 행 번호 + 열 번호가 작은 토끼
int aRC = a.r + a.c;
int bRC = b.r + b.c;
if (aRC != bRC) return aRC < bRC;
// 3. 행 번호가 작은 토끼
if (a.r != b.r) return a.r < b.r;
// 4. 열 번호가 작은 토끼
if (a.c != b.c) return a.c < b.c;
// 5. ID가 작은 토끼
return a.id < b.id;
}경주 시작 준비
문제에서 주어진 대로 입력을 받는다.
토끼의 경우는 고유번호(id)와 이동해야 하는 거리(d)를 입력받고 우선순위 큐에 push한다.
void input()
{
scanf("%d %d %d", &N, &M, &P);
hn = 0; // 우선순위 큐 초기화
for (int p = 0; p < P; p++)
{
int id, d;
scanf("%d %d", &id, &d);
RABBIT rabbit = { 0 };
rabbit.id = id;
rabbit.d = d;
rabbit.r = 1; // (1, 1)에서 시작
rabbit.c = 1;
push(rabbit);
}
}경주 진행
경주 진행은 다음과 같이 실행된다.
0) 현재 라운드에 해당하는 토끼의 check를 모두 0으로 초기화한다. (check = 해당 race에서 선택된 토끼)
ㄴ 우선순위 큐는 완전 이진트리므로, index(= 1 ~ hn)를 이용해 배열에 직접 접근할 수 있다.
1) 우선 순위가 높은 토끼를 우선순위 큐에서 pop한다.
2) 해당 토끼가 갈 수 있는 4개의 위치를 구해본다. (rc[0 ~ 3])
3) 4개의 위치 중 우선순위가 높은 칸을 선택한다.
4) 남은 토끼의 점수를 증가한다.
ㄴ 현재 우선순위 큐에는 선택한 토끼를 제외한 모든 토끼가 있다.
ㄴ 마찬가지로 index(= 1 ~ hn)로 접근할 수 있다. (pop을 했기 때문에 0번의 hn과 값이 다르다.)
5) 선택한 토끼를 움직이고, 점프 횟수와 check 표시를 하고 다시 우선순위 큐에 넣는다.
6) 뽑힌 토끼 중 가장 우선순위가 높은 (isMaxRabbit) 토끼에게 추가 점수를 준다.
void race(int k, int s)
{
// 0. 선택된 토끼 표시 초기화
for (int i = 1; i <= hn; i++) heap[i].check = 0;
for (int count = 0; count < k; count++)
{
// 1. 우선 순위가 높은 토끼 선택
RABBIT rabbit = pop();
// 2. 4방향 좌표 확인
RC rc[4] = { 0 }; // up, down, left, right
rc[0] = moveUp(rabbit);
rc[1] = moveDown(rabbit);
rc[2] = moveLeft(rabbit);
rc[3] = moveRight(rabbit);
// 3. 우선순위가 높은 칸 선택
RC moveRC = { 0 };
for (int d = 0; d < 4; d++)
if (isMaxRC(rc[d], moveRC))
moveRC = rc[d];
// 4. 나머지 토끼 점수 추가
for (int i = 1; i <= hn; i++)
heap[i].score += (moveRC.r + moveRC.c);
// 5. 선택된 토끼 위치 변경 및 정보 갱신
rabbit.r = moveRC.r;
rabbit.c = moveRC.c;
rabbit.jumpCount++;
rabbit.check = 1;
push(rabbit); // 다시 우선순위 큐에 추가
}
// 6. 한 번이라도 뽑힌 (check = 1) 토끼 중, 가장 우선순위(isMaxRabbit)가 높은 토끼 선택
int index = -1;
RABBIT selectRabbit = { 0 };
for (int i = 1; i <= hn; i++)
{
if (heap[i].check == 0) continue;
if (isMaxRabbit(heap[i], selectRabbit))
{
index = i;
selectRabbit = heap[i];
}
}
heap[index].score += s;
}
여기서 moveUp을 구현해 보자.
먼저 규칙을 찾는다.
만약 토끼가 N = 6이고 row = 2에서 moveUp을 해보자.
move = 1 → row = 1
move = 2 → row = 0 (좌표 범위 밖) → row = 2, 방향 변경 ↓
move = 3 → row = 3
...
move = 7 → row = 7 (좌표 범위 밖) → row = 5, 방향 변경 ↑
move = 8 → row = 4
...
move = 10 → row = 2 (원래 위치)
그림으로 그려보면 다음과 같다.
만약 row = 3인 경우라면 아래의 그림과 같다.
그림을 보고 규칙을 찾아보면 다음과 같다.
1) 이동할 위치는 2 * ( N - 1 ) 주기로 반복된다. 따라서 move = d % (2 * ( N - 1) ) 칸만 움직이면 된다.
2) rabbit.r - move가 1보다 크다면 땅을 넘지 않는 칸이 된다.
3) move가 rabbit.r + N - 2 이하인 경우는 내려가는 칸이다.
ㄴ 이 경우 실제 좌표는 move - (rabbit.r - 1) + 1이 된다.
4) 나머지의 경우, N에서 (움직이는 횟수 - (땅을 넘지 않는 검은색 칸) - (내려가는 빨간 칸 N - 1개)) 만큼 올라간다.
ㄴ실제 좌표는 N - (move - (rabbit.r - 1) - (N - 1))가 된다.
코드로 구현하면 다음과 같다.
RC moveUp(RABBIT rabbit)
{
RC ret = { 0 };
int r = rabbit.r;
int d = rabbit.d;
int move = d % (2 * (N - 1)); // 움직여야 할 칸 수
if ((rabbit.r - move) >= 1) ret.r = rabbit.r - move;
else
{
if (move <= (rabbit.r + N - 2))
ret.r = move - (rabbit.r - 1) + 1;
else
ret.r = N - (move - (rabbit.r - 1) - (N - 1));
}
ret.c = rabbit.c;
return ret;
}
moveDown은 복잡하게 다시 규칙을 찾을 필요 없이 대칭을 이용하면 된다.
(전체 좌표 + 1) 에서 현재 토끼의 좌표를 빼고 올라간 후,
그 결과를 (전체 좌표 + 1)에서 해당 좌표를 빼면 내려가는 것과 같은 결과가 된다.
RC moveDown(RABBIT rabbit)
{
// 대칭을 이용
RABBIT mirror = rabbit;
mirror.r = (N + 1) - rabbit.r;
RC ret = moveUp(mirror);
ret.r = (N + 1) - ret.r;
return ret;
}
moveLeft는 N을 M으로, r을 c로 변경하면 되고, moveRight도 마찬가지로 대칭을 이용하면 된다.
RC moveLeft(RABBIT rabbit)
{
RC ret = { 0 };
int c = rabbit.c;
int d = rabbit.d;
int move = d % (2 * (M - 1)); // 움직여야 할 칸 수
if ((rabbit.c - move) >= 1) ret.c = rabbit.c - move;
else
{
if (move <= (rabbit.c + M - 2))
ret.c = move - (rabbit.c - 1) + 1;
else
ret.c = M - (move - (rabbit.c - 1) - (M - 1));
}
ret.r = rabbit.r;
return ret;
}
RC moveRight(RABBIT rabbit)
{
// 대칭을 이용
RABBIT mirror = rabbit;
mirror.c = (M + 1) - rabbit.c;
RC ret = moveLeft(mirror);
ret.c = (M + 1) - ret.c;
return ret;
}
그리고 위에서 구한 4개의 좌표를 배열에 저장한다.
// 2. 4방향 좌표 확인
RC rc[4] = { 0 }; // up, down, left, right
rc[0] = moveUp(rabbit);
rc[1] = moveDown(rabbit);
rc[2] = moveLeft(rabbit);
rc[3] = moveRight(rabbit);
4개 좌표 중 우선순위가 높은 칸을 선택한다.
// 3. 우선순위가 높은 칸 선택
RC moveRC = { 0 };
for (int d = 0; d < 4; d++)
if (isMaxRC(rc[d], moveRC))
moveRC = rc[d];
문제에서 좌표에 대해 요구하는 우선순위는 다음과 같다.
int isMaxRC(RC a, RC b)
{
// 1. 행 번호 + 열 번호가 큰 칸
int aRC = a.r + a.c;
int bRC = b.r + b.c;
if (aRC != bRC) return aRC > bRC;
// 2. 행 번호가 큰 칸
if (a.r != b.r) return a.r > b.r;
// 3. 열 번호가 큰 칸
return a.c > b.c;
}
우선순위가 높은 좌표를 이용해 나머지 토끼에 모두 점수를 추가한다.
점수는 int 범위를 넘어갈 수 있어서 구조체에 long long으로 선언해두었다.
우선순위 큐는 완전 이진트리이기 때문에 1부터 heap index = hn까지 배열로 접근할 수 있다.
또한, 현재 우선순위 큐에는 race 초기에 선택한 토끼가 없다. (해당 토끼는 점수를 추가하지 않음)
// 4. 나머지 토끼 점수 추가
for (int i = 1; i <= hn; i++)
heap[i].score += (moveRC.r + moveRC.c);
이제 선택한 토끼를 실제로 이동하고, 점프 횟수를 증가하고, 선택 표시를 한다.
그리고 다시 우선순위 큐에 push한다.
// 5. 선택된 토끼 위치 변경 및 정보 갱신
rabbit.r = moveRC.r;
rabbit.c = moveRC.c;
rabbit.jumpCount++;
rabbit.check = 1;
push(rabbit); // 다시 우선순위 큐에 추가
check 표시된 토끼 중에 가장 우선순위가 높은 토끼를 선택해 점수에 S를 추가한다.
여기서 우선순위는 우선순위 큐의 우선순위와 다른 조건이다.
// 6. 한 번이라도 뽑힌 (check = 1) 토끼 중, 가장 우선순위(isMaxRabbit)가 높은 토끼 선택
int index = -1;
RABBIT selectRabbit = { 0 };
for (int i = 1; i <= hn; i++)
{
if (heap[i].check == 0) continue;
if (isMaxRabbit(heap[i], selectRabbit))
{
index = i;
selectRabbit = heap[i];
}
}
heap[index].score += S;
문제에서 요구한 조건대로 isMaxRabbit을 구현하였다.
int isMaxRabbit(RABBIT a, RABBIT b)
{
// 1. 현재 서 있는 행 번호 + 열 번호가 큰 토끼
int aRC = a.r + a.c;
int bRC = b.r + b.c;
if (aRC != bRC) return aRC > bRC;
// 2. 행 번호가 큰 토끼
if (a.r != b.r) return a.r > b.r;
// 3. 열 번호가 큰 토끼
if (a.c != b.c) return a.c > b.c;
// 4. ID가 큰 토끼
return a.id > b.id;
}이동거리 변경
전체 heap에서 해당되는 ID의 이동거리를 L배하면 된다.
void change(int pid_t, int l)
{
for (int i = 1; i <= hn; i++)
if (heap[i].id == pid_t) heap[i].d *= l;
}최고의 토끼 선정
전체 heap에서 가장 점수가 높은 토끼를 찾아서 출력한다.
void select()
{
ll maxScore = 0;
for (int i = 1; i <= hn; i++)
if (maxScore < heap[i].score) maxScore = heap[i].score;
printf("%lld\n", maxScore);
}전체 코드는 다음과 같다.
#include <stdio.h>
typedef long long ll;
#define MAX (2000 + 100)
#define START (100)
#define RACE (200)
#define CHANGE (300)
#define SELECT (400)
int Q, COMMAND, N, M, P;
typedef struct st1
{
int r;
int c;
}RC;
typedef struct st2
{
int r;
int c;
int id;
int d;
int check;
int jumpCount;
ll score;
}RABBIT;
RABBIT heap[MAX];
int hn;
int isMinRabbit(RABBIT a, RABBIT b)
{
// 1. 점프 횟수가 적은 토끼
if (a.jumpCount != b.jumpCount) return a.jumpCount < b.jumpCount;
// 2. 현재 서 있는 행 번호 + 열 번호가 작은 토끼
int aRC = a.r + a.c;
int bRC = b.r + b.c;
if (aRC != bRC) return aRC < bRC;
// 3. 행 번호가 작은 토끼
if (a.r != b.r) return a.r < b.r;
// 4. 열 번호가 작은 토끼
if (a.c != b.c) return a.c < b.c;
// 5. ID가 작은 토끼
return a.id < b.id;
}
int isMaxRC(RC a, RC b)
{
// 1. 행 번호 + 열 번호가 큰 칸
int aRC = a.r + a.c;
int bRC = b.r + b.c;
if (aRC != bRC) return aRC > bRC;
// 2. 행 번호가 큰 칸
if (a.r != b.r) return a.r > b.r;
// 3. 열 번호가 큰 칸
return a.c > b.c;
}
int isMaxRabbit(RABBIT a, RABBIT b)
{
// 1. 현재 서 있는 행 번호 + 열 번호가 큰 토끼
int aRC = a.r + a.c;
int bRC = b.r + b.c;
if (aRC != bRC) return aRC > bRC;
// 2. 행 번호가 큰 토끼
if (a.r != b.r) return a.r > b.r;
// 3. 열 번호가 큰 토끼
if (a.c != b.c) return a.c > b.c;
// 4. ID가 큰 토끼
return a.id > b.id;
}
RABBIT pop()
{
RABBIT ret, tmp;
ret = heap[1];
heap[1] = heap[hn];
heap[hn].jumpCount = 0x7fff0000;
heap[hn].r = 100001; // r + c = overflow 방지를 위해 0x7fff0000을 사용하지 않음.
heap[hn].c = 100001;
heap[hn--].id = 0x7fff0000;
for (register int i = 1; i * 2 <= hn;)
{
if (isMinRabbit(heap[i], heap[i * 2]) && isMinRabbit(heap[i], heap[i * 2 + 1])) break;
else if (isMinRabbit(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
i = i * 2 + 1;
}
}
return ret;
}
void push(RABBIT x)
{
RABBIT tmp;
heap[++hn] = x;
for (int i = hn; i > 1; i /= 2)
{
if (isMinRabbit(heap[i / 2], heap[i])) return;
tmp = heap[i / 2];
heap[i / 2] = heap[i];
heap[i] = tmp;
}
}
void printRabbit(RABBIT r)
{
printf("rabbit id %d, d %d, (%d, %d), jump : %d, score %d\n", r.id, r.d, r.r, r.c, r.jumpCount, r.score);
}
void printAll()
{
for (int i = 1; i <= hn; i++)
printRabbit(heap[i]);
printf("======================================\n");
}
void input()
{
scanf("%d %d %d", &N, &M, &P);
hn = 0; // 우선순위 큐 초기화
for (int p = 0; p < P; p++)
{
int id, d;
scanf("%d %d", &id, &d);
RABBIT rabbit = { 0 };
rabbit.id = id;
rabbit.d = d;
rabbit.r = 1; // (1, 1)에서 시작
rabbit.c = 1;
push(rabbit);
}
}
RC moveUp(RABBIT rabbit)
{
RC ret = { 0 };
int r = rabbit.r;
int d = rabbit.d;
int move = d % (2 * (N - 1)); // 움직여야 할 칸 수
if ((rabbit.r - move) >= 1) ret.r = rabbit.r - move;
else
{
if (move <= (rabbit.r + N - 2))
ret.r = move - (rabbit.r - 1) + 1;
else
ret.r = N - (move - (rabbit.r - 1) - (N - 1));
}
ret.c = rabbit.c;
return ret;
}
RC moveDown(RABBIT rabbit)
{
// 대칭을 이용
RABBIT mirror = rabbit;
mirror.r = (N + 1) - rabbit.r;
RC ret = moveUp(mirror);
ret.r = (N + 1) - ret.r;
return ret;
}
RC moveLeft(RABBIT rabbit)
{
RC ret = { 0 };
int c = rabbit.c;
int d = rabbit.d;
int move = d % (2 * (M - 1)); // 움직여야 할 칸 수
if ((rabbit.c - move) >= 1) ret.c = rabbit.c - move;
else
{
if (move <= (rabbit.c + M - 2))
ret.c = move - (rabbit.c - 1) + 1;
else
ret.c = M - (move - (rabbit.c - 1) - (M - 1));
}
ret.r = rabbit.r;
return ret;
}
RC moveRight(RABBIT rabbit)
{
// 대칭을 이용
RABBIT mirror = rabbit;
mirror.c = (M + 1) - rabbit.c;
RC ret = moveLeft(mirror);
ret.c = (M + 1) - ret.c;
return ret;
}
void race(int k, int s)
{
// 0. 선택된 토끼 표시 초기화
for (int i = 1; i <= hn; i++) heap[i].check = 0;
for (int count = 0; count < k; count++)
{
// 1. 우선 순위가 높은 토끼 선택
RABBIT rabbit = pop();
// 2. 4방향 좌표 확인
RC rc[4] = { 0 }; // up, down, left, right
rc[0] = moveUp(rabbit);
rc[1] = moveDown(rabbit);
rc[2] = moveLeft(rabbit);
rc[3] = moveRight(rabbit);
// 3. 우선순위가 높은 칸 선택
RC moveRC = { 0 };
for (int d = 0; d < 4; d++)
if (isMaxRC(rc[d], moveRC))
moveRC = rc[d];
// 4. 나머지 토끼 점수 추가
for (int i = 1; i <= hn; i++)
heap[i].score += (moveRC.r + moveRC.c);
// 5. 선택된 토끼 위치 변경 및 정보 갱신
rabbit.r = moveRC.r;
rabbit.c = moveRC.c;
rabbit.jumpCount++;
rabbit.check = 1;
push(rabbit); // 다시 우선순위 큐에 추가
}
// 6. 한 번이라도 뽑힌 (check = 1) 토끼 중, 가장 우선순위(isMaxRabbit)가 높은 토끼 선택
int index = -1;
RABBIT selectRabbit = { 0 };
for (int i = 1; i <= hn; i++)
{
if (heap[i].check == 0) continue;
if (isMaxRabbit(heap[i], selectRabbit))
{
index = i;
selectRabbit = heap[i];
}
}
heap[index].score += s;
}
void change(int pid_t, int l)
{
for (int i = 1; i <= hn; i++)
if (heap[i].id == pid_t) heap[i].d *= l;
}
void select()
{
ll maxScore = 0;
for (int i = 1; i <= hn; i++)
if (maxScore < heap[i].score) maxScore = heap[i].score;
printf("%lld\n", maxScore);
}
int main(void)
{
scanf("%d", &Q);
for (int q = 0; q < Q; q++)
{
scanf("%d", &COMMAND);
if (COMMAND == START) input();
else if (COMMAND == RACE)
{
int k, s;
scanf("%d %d", &k, &s);
race(k, s);
}
else if (COMMAND == CHANGE)
{
int pid_t, l;
scanf("%d %d", &pid_t, &l);
change(pid_t, l);
}
else if (COMMAND == SELECT)
{
select();
}
}
return 0;
}